18. Two pointers

A. General Introduction

B. Leetcode Problems

1268. Search Suggestions System

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example:

Input: products = [“mobile”,“mouse”,“moneypot”,“monitor”,“mousepad”], searchWord = “mouse”
Output: [
    [“mobile”,“moneypot”,“monitor”],
    [“mobile”,“moneypot”,“monitor”],
    [“mouse”,“mousepad”],
    [“mouse”,“mousepad”],
    [“mouse”,“mousepad”]
]
Explanation: products sorted lexicographically = [“mobile”,“moneypot”,“monitor”,“mouse”,“mousepad”]
After typing m and mo all products match and we show user [“mobile”,“moneypot”,“monitor”]
After typing mou, mous and mouse the system suggests [“mouse”,“mousepad”]

Key Ideas

• Sort the products lexicographically
• Iterate through the searchWord and move the left and right pointer accordingly if the position of current character index does not match with the position of the character in the product
• Add the first three words within the left and right pointers

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:

        result = []
        l, r = 0, len(products)-1

        products.sort()

        for i, c in enumerate(searchWord):

            while l<= r and (len(products[l]) <= i or products[l][i] != c):
                l += 1

            while l<=r and (len(products[r]) <= i or products[r][i] != c):
                r -= 1

            out = [p for p in products[l:min(l+3,r+1)]]
            result.append(out)

        return result

28. Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example:

Input: needle = “sad”, haystack = “sadbutsad”
Output: 0 Explanation: The first occurrence of “sad” is at index 0.

Key Ideas

• start index moves through the string; Have an additional pointer i to move through the haystack until character at i matches the character at index i of needle
• If i equals to the len(needle)-1, return the start

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:

        if len(needle) > len(haystack):
            return -1

        start = 0

        while start < len(haystack):

            idx = 0

            while idx < len(needle) and start+idx < len(haystack) and haystack[start+idx] == needle[idx]:
                idx += 1

            if idx-1 == len(needle)-1:
                return start

            start += 1

        return -1

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example:

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [
    [-1, 0, 1],
    [-1, -1, 2]
]
Explanation:
nums[0] + nums[1] + nums[2] = 0
nums[1] + nums[2] + nums[4] = 0
nums[0] + nums[3] + nums[4] = 0
The distinct triplets are [-1, 0, 1] and [-1, -1, 2]. Notice that order doesn’t matter.

Key Ideas

• To ensure the duplicates have been removed, sort the array; adjacent elements are the same, skip them
  • Iterate through the array and perform twosum on the remaining array

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        idx = 0
        result = []
        nums.sort()

        for idx in range(len(nums)):

            if idx > 0 and nums[idx] == nums[idx-1]:
                continue

            l, r = idx+1, len(nums)-1

            while l < r:

                threeSum = nums[idx] + nums[l] + nums[r]

                if threeSum > 0:
                    r -= 1

                elif threeSum < 0:
                    l += 1

                else:
                    result.append([nums[idx], nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1


        return result

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example:

Key Ideas

• Have two pointers, left and right at the beginning and the end of the array
  • The width of the container is always going to decrease, because we move the pointers towards the center
  • Hence, we need to maximize the height of the container
    • Move the pointer with the smaller height towards the center

class Solution:
    def maxArea(self, height: List[int]) -> int:

        max_area = float("-inf")

        l,r = 0, len(height)-1

        while l < r:

            lh, rh = height[l], height[r]

            w = r-l
            h = min(lh, rh)

            max_area = max(max_area, w*h)

            if lh < rh:
                l += 1
            else:
                r -= 1

        return max_area

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example:

Key Ideas

• At each index, the following is the amount of water that can be trapped
  • $\text{min}(\text{max_left}, \text{max_right})-\text{height}[i]$

class Solution:
    def trap(self, height: List[int]) -> int:

        m = len(height)
        area = 0

        leftH = [0]*m
        rightH = [0]*m

        leftMax = float("-inf")
        for i in range(1,m):

            leftMax = max(height[i-1], leftMax)
            leftH[i] = leftMax

        rightMax = float("-inf")
        for i in range(m-2,-1, -1):

            rightMax = max(height[i+1], rightMax)
            rightH[i] = rightMax

        for i in range(m):

            a = min(leftH[i], rightH[i]) - height[i]
            area += max(0, a)

        return area