[Algorithm] Two pointers | Sliding Window

Two Pointers

• Leetcode # 3. Longest Substring Without Repeating Characters
• LeetCode # 11. Container With Most Water
• Leetcode # 26. Remove Duplicates from Sorted Array
• Leetcode # 80. Remove Duplicates from Sorted Array II
• Leetcode # 88. Merge Sorted Array
• Leetcode # 167. Two Sum II – Input Array Is Sorted
• Leetcode # 209. Minimum Size Subarray Sum
• Leetcode # 239. ⭐️ Sliding Window Maximum
• Leetcode # 424. Longest Repeating Character Replacement
• Leetcode # 438. Find All Anagrams in a String
• Leetcode # 487. Max Consecutive Ones II
• Leetcode # 567. Permutation in String
• Leetcode # 632. Smallest Range Covering Elements from K Lists
• Leetcode # 643. Maximum Average Subarray I
• Leetcode # 977. Squares of a Sorted Array
• Leetcode # 1004. Max Consecutive Ones III
• Leetcode # 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
• Leetcode # 1475. Final Prices With a Special Discount in a Shop
• Leetcode # 1493. Longest Subarray of 1’s After Deleting One Element
• Leetcode # 2024. Maximize the Confusion of an Exam
• Leetcode # 2109. Adding Spaces to a String
• Leetcode # 2444. Count Subarrays With Fixed Bounds
• Leetcode # 2825. Make String a Subsequence Using Cyclic Increments
• Leetcode # 2875. Minimum Size Subarray in Infinite Array
• Leetcode # 2981. Find Longest Special Substring That Occurs Thrice I
• Leetcode # 3152. Special Array II

收縮型 One Input, Opposite Ends (相反的兩端：[left → … ← right])

left 和 right 兩個 pointer
為 opposite ends (相反的兩端；起始於起點和終點，並越來越靠近)

Template

def fn(arr):
  ans = 0
  left, right = 0, len(arr) - 1

  while left < right:
    # do some logic here with left and right
        
    if CONDITION:
      left += 1
    else:
      right -= 1
    
  return ans

例題

• LeetCode # 11. Container With Most Water
• Leetcode # 167. Two Sum II – Input Array Is Sorted
• Leetcode # 977. Squares of a Sorted Array

平行型 Two Inputs, Exhaust Both (消耗兩者：[i → … ] [j → … ])

Template

def fn(arr1, arr2):
  i = j = ans = 0
  while i < len(arr1) and j < len(arr2):
    # do some logic here
    if CONDITION:
      i += 1
    else:
      j += 1
    
  while i < len(arr1):
    # do logic
    i += 1
    
  while j < len(arr2):
    # do logic
    j += 1
    
  return ans

例題

• Leetcode # 88. Merge Sorted Array

滑動型 Sliding Window ([left → … right → … ])

要訣

每當 sliding window 變動時，從零計算（重要資訊的）總體狀態 (O(n²))
從 sliding window 變動的左右邊界範圍計算差距
再得以併用舊的總體狀態，得知新的總體狀態 (O(n))

思考

1. 合法構築 sliding window w 的條件
   （在 sliding window 不合法時，調整 left 使 sliding window 回到合法狀態）
2. 如何遵循上述要訣並從 sliding window 中獲得目標解答的方法 f(w)
   （return best([f(w) for w in all_sliding_windows])）

Template

sliding_window := arr[left:right + 1]

left := left pointer of sliding window (start of sliding window)
length := length of slide window = right – left + 1
right := right pointer of sliding window (end of sliding window) = left + length – 1

curr := f(current_sliding_window)
ans := best([f(w) for w in all_sliding_window])

def fn(arr):
  ans = left = curr = 0
  for right in range(len(arr)):
    # do logic here to add arr[right] to curr

    while WINDOW_CONDITION_BROKEN:
      # remove arr[left] from curr
      left += 1

    # update ans
    
  return ans

使用例

• Leetcode # 239. Sliding Window Maximum

優化 Sliding Window 作例 (當 sliding window 不合法時調整 left)

• Leetcode # 3. Longest Substring Without Repeating Characters
• Leetcode # 2444. Count Subarrays With Fixed Bounds

例題

• Leetcode # 3. Longest Substring Without Repeating Characters
• Leetcode # 209. Minimum Size Subarray Sum
• Leetcode # 239. ⭐️ Sliding Window Maximum
• Leetcode # 424. Longest Repeating Character Replacement
• Leetcode # 438. Find All Anagrams in a String
• Leetcode # 487. Max Consecutive Ones II
• Leetcode # 567. Permutation in String
• Leetcode # 632. Smallest Range Covering Elements from K Lists
• Leetcode # 643. Maximum Average Subarray I
• Leetcode # 1004. Max Consecutive Ones III
• Leetcode # 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
• Leetcode # 1493. Longest Subarray of 1’s After Deleting One Element
• Leetcode # 2024. Maximize the Confusion of an Exam
• Leetcode # 2444. Count Subarrays With Fixed Bounds
• Leetcode # 2875. Minimum Size Subarray in Infinite Array
• Leetcode # 2981. Find Longest Special Substring That Occurs Thrice I
• Leetcode # 3152. Special Array II

Fast & Slow Pointer｜Floyd’s Cycle Detection Algorithm｜Hare & Tortoise Algorithm

\begin{align}
F &:= \text{length of nodes before cycle} \\
C &:= \text{length of nodes in cycle}
\end{align}

將 noncyclic nodes 標記為 –F to -1
將 cycle 裡的 nodes 標記為 0 to  C – 1
node (-F) 為 list 的起點; node 0 則是 Cycle 的起點

1 – a.
hare 的速度是 tortoise 的兩倍
在 iteration F
tortoise 到達 node 0
而 hare 則走了 2F 步到達 node h 
※ h = F % C ⇒ h = F – nC ⇒ F = h + nC

1 – b
再經過 C – h iterations 後
tortoise 位於 node (C – h)
hare 也會在 node (C – h) 和 tortoise 相遇
※ h + 2(C – h) = 2C – h; (2C – h) % C = C – h

如果這個 list 沒有 cycle，hare 會比 tortoise 先到達終點

2.
將 tortoise 移回 node (-F)，hare 留在 node (C – h) 
並將兩者的速度皆設定為 1 
則再經過 F iterations 後
tortoise 的位置會在 Cycle 的起點 node 0
※ –F + F = 0
hare的位置也會在 Cycle 的起點 node 0
※ (C – h) + F = (C – h) + (h + nC) = (n + 1)C; ((n + 1)C) % C = 0

由以上的步驟，我們可以藉此確定起點的位置

例題

• Leetcode # 141. Linked List Cycle
• Leetcode # 142. Linked List Cycle II (Floyd’s Tortoise🐢 and Hare🐇)

Last Updated on 2023/09/10 by A1go