# 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

## Code

```
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:0Explanation: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`

## Code

```
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

- Iterate through the array and perform

## Code

```
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

## Code

```
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]$

## Code - O(1) Space complexity

```
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
```