Thuc Nguyen's ADSA Course - Lecture 18. Two Pointer Technique

--- title: Thuc Nguyen's ADSA Course - Lecture 18. Two Pointer Technique tags: Advanced Data Structures and Algorithms Course description: View the slide with "Slide Mode". type: slide slideOptions: theme: white # transition: 'fade' # parallaxBackgroundImage: 'https://s3.amazonaws.com/hakim-static/reveal-js/reveal-parallax-1.jpg' --- ## 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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.