## Lecture 18. Two Pointer Technique
- Old and new state
- Slow and fast runner
- Left and right boundary
- Pointer-1 and pointer-2 from two sequences
- Start and end of sliding window
Note:
https://www.pluralsight.com/guides/algorithm-templates:-two-pointers-part-1
https://www.pluralsight.com/guides/algorithm-templates:-two-pointers-part-2
---
### Two Pointer Technique
- Involves using **two pointers** to keep track of indices, simplify logic, and save time and space.
- Types:
- Old and new state: `old, new = new, cur_result`
- Slow and fast runner: `slow-> fast->->`
- Left and right boundary: `|left-> ... <-right|`
- Pointer-1 and pointer-2 from two sequences: `p1-> p2->`
- Start and end of sliding window: `|start-> ... end->|`
---
#### Two Pointer Technique
<img src="https://cdn.ucode.vn/uploads/1/upload/kSdXhVPX.png" class="element-left content-img" />
---
### Slow and Fast Runner
- Template: fast runner grows each iteration and slow runner grows with some restrictions
```python=
def slow_fast_runner(self, seq):
# initialize slow runner
slow = seq[0] # for index: slow = 0
# fast-runner grows each iteration generally
for fast in range(seq): # for index: range(len(seq))
#slow-runner grows with some restrictions
if self.slow_condition(slow):
slow = slow.next # for index: slow += 1
# process logic before or after pointers movement
self.process_logic(slow, fast)
```
---
#### Slow and Fast Runner:
- Example: Given a sorted array `nums`, remove the duplicates in place such that each element appear only once and return the new length.
Note:
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
---
#### Slow and Fast Runner
```python=
def removeDuplicates(nums: 'List[int]') -> int:
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
# if current element is not duplicate,
# slow runner grows one step and copys the current value
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
```
---
#### Slow and Fast Runner
- Example: Given a linked list, remove the $n$-th node from the end of the list and return its head.
<img src="https://cdn.ucode.vn/uploads/1/upload/GQNInWDH.png" class="element-left content-img" />
Note:
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
---
#### Slow and Fast Runner
```python=
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
slow, fast = head
for i in range(n): # fast runner moves n step first
fast = fast.next
while fast.next: # slow and fast moves together
slow, fast = slow.next, fast.next
slow.next = slow.next.next
return head
```
---
#### Slow and Fast Runner
- Detecting cycles in a linked list data structure: move the fast pointer twice as quickly as the slow pointer so the distance between them increases by 1 at each step.
<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/linked-lists/slow-and-fast-pointers-step-1.svg" loading="lazy" alt="Step Ten" style="width: 70%; max-width: 100%; margin-left: auto; margin-right: auto; display: block;">
Note:
https://algodaily.com/lessons/using-the-two-pointer-technique
---
#### Slow and Fast Runner
<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/linked-lists/slow-and-fast-pointers-step-2.svg" loading="lazy" alt="Step Eleven" style="width: 70%; max-width: 100%; margin-left: auto; margin-right: auto; display: block;">
---
#### Slow and Fast Runner
<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/linked-lists/slow-and-fast-pointers-step-3.svg" loading="lazy" alt="Step Twelve" style="width: 70%; max-width: 100%; margin-left: auto; margin-right: auto; display: block;">
---
#### Slow and Fast Runner
```python=
def has_cycle(head):
slow, fast = head, head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
```
Note:
https://algodaily.com/lessons/using-the-two-pointer-technique
---
### Old and New State
- Template: variables store intermediate states and participate in the calculation to generate new states
```python=
# old & new state: old, new = new, cur_result
def old_new_state(self, seq):
# initialize state
old, new = default_val1, default_val2
for element in seq:
# process current element with old state
old, new = new, self.process_logic(element, old)
```
---
#### Old and New State
- Example: calculating a Fibonacci number.
```python=
def fibonacci(n: int) -> int:
a, b = 0, 1
for i in range(n + 1):
a, b = b, a + b
return a
```
---
#### Old and New State
- Example: Determine the maximum amount of money you can steal tonight without robbing adjacent houses.
- Example:
```text
Input: nums = [2,7,9,1,1,3,0]
Output: 14
Explanation: 2 + 9 + 3 = 14.
```
Note:
https://leetcode.com/problems/house-robber/
---
#### Old and New State
```python=
def rob(nums: List[int]) -> int:
last, now = 0, 0
for i in nums:
last, now = now, max(last + i, now)
return now
```
---
#### Old and New State
- A message containing letters from A-Z can be encoded into numbers using the following mapping:
```
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
```
- Given a non-empty string containing only digits, determine the total number of ways to decode it.
Note:
https://leetcode.com/problems/decode-ways/
---
#### Old and New State
- Example: Given a non-empty string containing only digits, determine the total number of ways to decode it.
```text
Input: s = "226"
Output: 3
Explanation: "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
```
---
#### Old and New State
```python=
def numDecodings(s: str) -> int:
if len(s) > 0 and s[0] > '0':
a, b = 1, 1
else:
return 0
for i in range(1, len(s)):
if s[i] == '0':
if s[i - 1] > '2' or s[i - 1] == '0':
return 0
a, b = 0, a
elif s[i - 1] == '1' or (s[i - 1] == '2' and s[i] < '7'):
a, b = b, a + b
else:
a, b = b, b
return b
```
---
### Left and Right Boundary
- Putting pointers on the left-most side and right-most side.
- One pointer starts from the beginning, while the other pointer starts from the end.
- They move toward each other until they meet in the middle.
---
#### Left and Right Boundary: template
```python=
def left_right_boundary(self, seq):
left, right = 0, len(seq) - 1
while left < right:
# left index moves when satisfy the condition
if self.left_condition(left):
left += 1
# right index move when satisfy the condition
if self.right_condition(right):
right -= 1
# process logic before or after pointers movement
self.process_logic(left, right)
```
---
#### Left and Right Boundary
- Example: Binary search
```python=
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
# find the target, change to your comparison condition as you need
if arr[mid] == target:
break
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
```
---
#### Left and Right Boundary
- Example: Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
- Example:
```
Input: numbers = [2,3,4], target = 6
Output: [1,3]
```
Note:
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
---
#### Left and Right Boundary
```python=
def twoSum(numbers: 'List[int]', target: 'int') -> 'List[int]':
left, right = 0, len(numbers) - 1
while left < right:
if numbers[left] + numbers[right] == target:
return [left + 1, right + 1]
if numbers[left] + numbers[right] < target:
left += 1
else:
right -= 1
return [0, 0]
```
---
#### Left and Right Boundary
- Upgrade the two-sum problem to four-sum: Find all unique quadruplets in the array which gives the sum of target.
- https://leetcode.com/problems/4sum/
Note:
```python=
def fourSum(nums: 'List[int]', target: int) -> 'List[int]':
result, n = [], len(nums)
if n < 4: return result
nums = sorted(nums)
if sum(nums[-4:]) < target:
return result
for i in range(n - 3):
# boundary checker, stop early
if sum(nums[i:i + 4]) > target:
break
# right boundary checker
if nums[i] + sum(nums[-3:]) < target:
continue
# skip same element, but keep the first one
if i > 0 and nums[i] == nums[i - 1]:
continue
# simplify the problem to three sum
target2 = target - nums[i]
for j in range(i + 1, n - 2):
if sum(nums[j:j + 3]) > target2 or sum(nums[-3:]) < target2:
break
if nums[j] + sum(nums[-2:]) < target2:
continue
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# simplify the problem to two sum
target3 = target2 - nums[j]
left = j + 1
right = n - 1
while left < right:
if nums[left] + nums[right] == target3:
result.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif nums[left] + nums[right] < target3:
left += 1
else:
right -= 1
return result
```
---
#### Left and Right Boundary
- Find two lines, which together with x-axis form a container, such that the container contains the most water possible.
<img src="https://cdn.ucode.vn/uploads/1/upload/RMmyXxQM.png" class="element-left content-img" />
Note:
https://leetcode.com/problems/container-with-most-water/
---
#### Left and Right Boundary
```python=
def maxArea(height: 'List[int]') -> int:
left, right = 0, len(height) - 1
area_max = (right - left) * min(height[left], height[right])
while left < right:
# judge which side decide the area (shorter height)
if height[left] <= height[right]:
last_height = height[left]
# skip all the height less than current
while height[left] <= last_height and left < right:
left += 1
else:
last_height = height[right]
# skip all the height less than current
while height[right] <= last_height and left < right:
right -= 1
if left >= right:
return area_max
area_max = max(area_max, (right - left) * min(height[left], height[right]))
return area_max
```
---
### Two Pointers from Two Sequences
- Template:
```python=
def pointers_from_two_seq(self, seq1, seq2):
# init pointers
p1, p2 = 0, 0 # or seq1[0], seq2[0]
# or other condition
while p1 < len(seq1) and p2 < len(seq2):
# p1 index moves when satisfy the condition
if self.p1_condition(p1):
p1 += 1 # or p1 = next(seq1)
# p2 index move when satisfy the condition
if self.p2_condition(p2):
p2 += 1 # or p2 = next(seq2)
# process logic before or after pointers movement
self.process_logic(p1, p2)
```
---
#### Two Pointers from Two Sequences
- Merge two sorted linked lists and return a new list.
<img src="https://cdn.ucode.vn/uploads/1/upload/homCgxPi.png" class="element-left content-img" />
Note:
https://leetcode.com/problems/merge-two-sorted-lists/
---
#### Two Pointers from Two Sequences
```python=
class ListNode():
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(a: ListNode, b: ListNode) -> ListNode:
if not a or b and a.val > b.val:
a, b = b, a
if a:
a.next = mergeTwoLists(a.next, b)
return a
```
---
#### Two Pointers from Two Sequences
- Given list of words, find the shortest distance between these two words `word1` and `word2` in the list.
- Example:
```text
Input:
words = 'practice makes perfect coding makes'
word1 = 'makes'
word2 = 'coding'
Output: 1
```
Note:
https://www.codingninjas.com/studio/problems/shortest-word-distance-ii_1459114
https://leetcode.com/problems/shortest-word-distance-ii/
---
#### Two Pointers from Two Sequences
```python=
class WordDistance:
def __init__(self, words: 'List[str]'):
self.locations = defaultdict(list)
# Prepare a mapping from a word to all it's locations (indices).
for i, w in enumerate(words):
self.locations[w].append(i)
def shortest(self, word1: str, word2: str) -> int:
loc1, loc2 = self.locations[word1], self.locations[word2]
l1, l2 = 0, 0
min_diff = float("inf")
# Until the shorter of the two lists is processed
while l1 < len(loc1) and l2 < len(loc2):
min_diff = min(min_diff, abs(loc1[l1] - loc2[l2]))
if loc1[l1] < loc2[l2]:
l1 += 1
else:
l2 += 1
return min_diff
```
---
#### Two Pointers from Two Sequences
- Given an input string ($s$) and a pattern ($p$), implement wildcard pattern matching with support for '`?`' and '`*`'.
- Example:
```
Input: s = "aa", p = "*"
Output: true
Input: s = "cb", p = "?a"
Output: false
Input: s = "aa", p = "a"
Output: false
```
---
#### Two Pointers from Two Sequences
```python=
def isMatch(s: str, p: str) -> bool:
s_cur, p_cur, match, star = 0, 0, 0, -1
while s_cur < len(s):
# match sucess, both two pointers move forward
if p_cur < len(p) and (s[s_cur] == p[p_cur] or p[p_cur] == '?'):
s_cur += 1
p_cur += 1
# if matching star, record current state and try to match in greedy
elif p_cur < len(p) and p[p_cur] == '*':
match = s_cur
star = p_cur
p_cur += 1
# backtrack if match failed
elif star != -1:
p_cur = star + 1
match += 1
s_cur = match
else:
return False
# corner case: remove continuous star in the rest
while p_cur < len(p) and p[p_cur] == '*':
p_cur += 1
if p_cur == len(p):
return True
else:
return False
```
---
### Sliding Window
<img src="https://cdn.ucode.vn/uploads/1/upload/JSjobPNc.png" class="element-left content-img" />
---
#### Sliding Window: Template
```python=
def start_end_sliding_window(self, seq):
start, end = 0, 0
while end < len(seq):
# end pointer grows in the outer loop
end += 1
# start pointer grows with some restrict
while self.start_condition(start):
# process logic before pointers movement
self.process_logic1(start, end)
# start grows in the inner loop
start += 1
# or process logic after pointers movement
self.process_logic2(start, end)
```
---
#### Sliding Window
- Find maximum (or minimum) sum of a subarray of size $k$
- Example:
```
Input : arr[] = {100, 200, 300, 400}, k = 2
Output : 700
Input : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Output : 39
```
---
#### Sliding Window
```python=
def maxSum(arr, k):
n = len(arr)
max_sum = window_sum = sum(arr[:k])
for i in range(n - k):
window_sum = window_sum - arr[i] + arr[i + k]
max_sum = max(window_sum, max_sum)
return max_sum
```
---
#### Sliding Window
- Given a string, find the length of the longest substring without repeating characters.
- Examples:
```
Input: s = "bbbbb"
Output: 1
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
```
Note:
https://leetcode.com/problems/longest-substring-without-repeating-characters/
---
#### Sliding Window
```python=
def lengthOfLongestSubstring(s: str) -> int:
# create a default dict to maintain state
counter = defaultdict(int)
count, start, end, res = 0, 0, 0, 0
while end < len(s):
counter[s[end]] += 1
if counter[s[end]] > 1:
count += 1
end += 1
while count > 0:
counter[s[start]] -= 1
if counter[s[start]] > 0:
count -= 1
start += 1
# update maximum here
res = max(res, end - start)
return res
```
---
#### Sliding Window
- You have **two baskets**, and each basket can carry any quantity of fruit, but you want each basket to only carry **one type** of fruit each. Once you reach a tree with fruit that cannot fit in your baskets, you must stop. What is the total amount of fruit you can collect with this procedure?
Note:
https://leetcode.com/problems/fruit-into-baskets/
---
#### Sliding Window
- Examples:
```
Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.
Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
```
---
#### Sliding Window
```python=
def totalFruit(tree: 'List[int]') -> int:
counter = defaultdict(int)
count, start, end, res = 0, 0, 0, 0
while end < len(tree):
counter[tree[end]] += 1
if counter[tree[end]] == 1:
count += 1
end += 1
while count > 2:
counter[tree[start]] -= 1
if counter[tree[start]] == 0:
count -= 1
start += 1
res = max(res, end - start)
return res
```
---
## The End
{"title":"Thuc Nguyen's ADSA Course - Lecture 18. Two Pointer Technique","description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":19163,\"del\":509}]"}