🧊 Two Pointers & Sliding Window

[tpemeja]

Summary

• Patterns

  • Two Pointers: l/r inward; sorted/boundary.
  • Fast & Slow: 1x/2x or gap; cycle/middle/palindrome/Nth.
  • Window (fixed k): add R, drop L; eval at size k.
  • Window (variable): grow R, shrink L until valid; longest/shortest/count.

• Choose

  • Sorted ends/min–max → Two Pointers
  • Linked list/cycle → Fast & Slow
  • Exactly k-length metric → Fixed Window
  • “At most/at least” constraint → Variable Window

Details

✅ Two Pointers (start/end)

Summary (Key points):

• Keep two indices l (start) and r (end); move one inward per step using a monotone rule.
• Works best on sorted arrays or boundary-limited objectives (min/max of ends).
• Typical time O(n), space O(1). If sorting is needed first, total O(n log n).

Details

• Concept recap:

  • Maintain l = 0 and r = n - 1.
  • Each iteration: compute something from a[l], a[r], decide which side to move, ensure at least one pointer moves.

• Generic template:

  def two_pointers_template(a):
      l, r = 0, len(a) - 1
      while l < r:
          # compute from a[l], a[r]
          # if <condition>: l += 1
          # else: r -= 1
          pass

• Case 1: Two Sum II (sorted) — find pair equal to target

  • Rule: s = a[l] + a[r]; if s < target → l += 1; if s > target → r -= 1; if equal → return.
  • Time: O(n) after sort, Space: O(1).

  def two_sum_sorted(a, target):
      l, r = 0, len(a) - 1
      while l < r:
          s = a[l] + a[r]
          if s == target:
              return l, r  # or (a[l], a[r])
          if s < target:
              l += 1
          else:
              r -= 1
      return None

• Case 2: Container With Most Water — maximize area

  • Area = (r - l) * min(height[l], height[r]); move the shorter side.
  • Time: O(n), Space: O(1).

  def max_area(height):
      l, r = 0, len(height) - 1
      best = 0
      while l < r:
          h = min(height[l], height[r])
          best = max(best, (r - l) * h)
          if height[l] < height[r]:
              l += 1
          else:
              r -= 1
      return best

• Case 3: Trapping Rain Water (two-pointer)

  • Keep max_left and max_right; if max_left <= max_right, finalize at l; else at r.
  • Time: O(n), Space: O(1).

  def trap_rain_water(h):
      if len(h) < 3:
          return 0
      l, r = 0, len(h) - 1
      max_left, max_right = h[l], h[r]
      water = 0
      while l < r:
          if max_left <= max_right:
              l += 1
              if h[l] < max_left:
                  water += max_left - h[l]
              else:
                  max_left = h[l]
          else:
              r -= 1
              if h[r] < max_right:
                  water += max_right - h[r]
              else:
                  max_right = h[r]
      return water

• Case 4: 3Sum — unique triplets summing to zero

  • Sort; for each i, two-pointer on suffix for target = -a[i]; deduplicate i, l, r.
  • Time: O(n^2), Space: O(1) extra (excluding output).

  def three_sum(nums):
      nums.sort()
      n = len(nums)
      out = []
      i = 0
      while i < n - 2:
          a = nums[i]
          if a > 0:
              break
          l, r = i + 1, n - 1
          while l < r:
              s = a + nums[l] + nums[r]
              if s == 0:
                  out.append([a, nums[l], nums[r]])
                  lv, rv = nums[l], nums[r]
                  while l < r and nums[l] == lv: l += 1
                  while l < r and nums[r] == rv: r -= 1
              elif s < 0:
                  l += 1
              else:
                  r -= 1
          # skip duplicate anchors
          v = a
          while i < n - 2 and nums[i] == v:
              i += 1
      return out

• Case 5: Valid Palindrome (alnum, case-insensitive)

  • Skip non-alnum at both ends; compare casefolded chars; move both on match.
  • Time: O(n), Space: O(1).

  def is_palindrome_alnum(s):
      l, r = 0, len(s) - 1
      while l < r:
          while l < r and not s[l].isalnum():
              l += 1
          while l < r and not s[r].isalnum():
              r -= 1
          if s[l].casefold() != s[r].casefold():
              return False
          l += 1
          r -= 1
      return True

• Case 6: Squares of a Sorted Array

  • Compare abs at ends; place larger square at the back; move that side.
  • Time: O(n), Space: O(n) for output.

  def sorted_squares(a):
      n = len(a)
      l, r = 0, n - 1
      out = [0] * n
      w = n - 1
      while l <= r:
          if abs(a[r]) >= abs(a[l]):
              out[w] = a[r] * a[r]
              r -= 1
          else:
              out[w] = a[l] * a[l]
              l += 1
          w -= 1
      return out

• Case 7: Count pairs with sum < target (block counting)

  • If a[l] + a[r] < target, then all pairs (l..r-1, r) are valid → add (r - l); l += 1. Else r -= 1.
  • Time: O(n) after sort, Space: O(1).

  def count_pairs_less_than(a, target):
      a.sort()
      l, r = 0, len(a) - 1
      count = 0
      while l < r:
          if a[l] + a[r] < target:
              count += (r - l)
              l += 1
          else:
              r -= 1
      return count

• Complexity summary:

  • Pure start/end scans: O(n) time, O(1) extra space.
  • With sorting: O(n log n) + O(n) scan.
  • 3Sum/4Sum: O(n^2)/O(n^3) respectively.

✅ Fast and slow pointers

Summary (Key points):

• Two runners over a sequence: slow moves 1 step, fast moves 2 steps (or a fixed gap).
• Detect cycles, find cycle entry, find middle, compare halves (palindrome), remove N-th from end, or detect cycles in implicit graphs (arrays, number transforms).
• Typical time O(n), space O(1). Always guard fast and fast.next before advancing fast twice.

Details

• Concept recap:

  • Linked lists: slow = slow.next (1x), fast = fast.next.next (2x). If they ever meet → cycle exists.
  • After a meet, placing slow at head and moving both 1x leads them to the cycle’s entry.
  • Gap trick: advance fast by n steps, then move both to position slow at a desired spot.

• Generic templates:

  # Singly-linked list node
  class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  
  # Floyd's Tortoise-Hare (cycle detection)
  def has_cycle(head: ListNode) -> bool:
      slow = fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
          if slow is fast:
              return True
      return False
  
  # Gap trick (advance fast by k, then move both)
  def advance_with_gap(head: ListNode, k: int) -> ListNode | None:
      slow = fast = head
      for _ in range(k):
          if not fast: return None
          fast = fast.next
      while fast:
          slow = slow.next
          fast = fast.next
      return slow

• Case 1: Linked List Cycle — detect if a cycle exists

  • Rule: slow 1x, fast 2x; meet ⇒ cycle; fast hits None ⇒ no cycle.
  • Time: O(n), Space: O(1).

  def has_cycle(head: ListNode) -> bool:
      slow = fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
          if slow is fast:
              return True
      return False

• Case 2: Linked List Cycle II — find the cycle’s entry node

  • After meeting, set slow = head; move slow and fast 1x until they meet again → entry.
  • Time: O(n), Space: O(1).

  def detect_cycle_start(head: ListNode) -> ListNode | None:
      slow = fast = head
      # Phase 1: detect meeting point
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
          if slow is fast:
              break
      else:
          return None  # no cycle
      # Phase 2: find entry
      slow = head
      while slow is not fast:
          slow = slow.next
          fast = fast.next
      return slow

• Case 3: Middle of the Linked List

  • Move fast 2x, slow 1x; when fast ends, slow is middle (second middle for even length).
  • Time: O(n), Space: O(1).

  def middle_node(head: ListNode) -> ListNode:
      slow = fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
      return slow

• Case 4: Palindrome Linked List

  • Find middle, reverse second half, compare halves (optionally restore).
  • Time: O(n), Space: O(1).

  def is_palindrome_list(head: ListNode) -> bool:
      if not head or not head.next:
          return True
      # 1) find middle
      slow = fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
      # 2) reverse second half starting at slow
      prev, cur = None, slow
      while cur:
          nxt = cur.next
          cur.next = prev
          prev, cur = cur, nxt
      # 3) compare first half vs reversed second half
      p1, p2 = head, prev
      ok = True
      while p2:  # second half length <= first
          if p1.val != p2.val:
              ok = False
              break
          p1 = p1.next
          p2 = p2.next
      # (Optional) restore by reversing prev again
      return ok

• Case 5: Remove Nth Node From End of List — two pointers with a gap

  • Advance fast by n; then move both; slow stops before the node to remove.
  • Time: O(n), Space: O(1).

  def remove_nth_from_end(head: ListNode, n: int) -> ListNode:
      dummy = ListNode(0, head)
      slow = fast = dummy
      for _ in range(n):
          fast = fast.next
      while fast and fast.next:
          slow = slow.next
          fast = fast.next
      slow.next = slow.next.next
      return dummy.next

• Case 6: Find the Duplicate Number — Floyd over array indices

  • Treat i → nums[i] as next; duplicate is the cycle entry.
  • Time: O(n), Space: O(1).

  from typing import List
  
  def find_duplicate(nums: List[int]) -> int:
      slow = fast = nums[0]
      # Phase 1: meet
      while True:
          slow = nums[slow]
          fast = nums[nums[fast]]
          if slow == fast:
              break
      # Phase 2: entry
      slow = nums[0]
      while slow != fast:
          slow = nums[slow]
          fast = nums[fast]
      return slow

• Case 7: Happy Number — cycle detection on number transform

  • f(n) = sum of squares of digits; meeting at 1 ⇒ happy; meeting elsewhere ⇒ cycle (unhappy).
  • Time: O(log n) per transform step, Space: O(1).

  def is_happy(n: int) -> bool:
      def next_val(x: int) -> int:
          s = 0
          while x:
              x, d = divmod(x, 10)
              s += d * d
          return s
      slow = next_val(n)
      fast = next_val(next_val(n))
      while slow != fast:
          slow = next_val(slow)
          fast = next_val(next_val(fast))
      return slow == 1

• Pitfalls and tips:

  • Always guard: while fast and fast.next before doing fast = fast.next.next.
  • For odd-length palindrome, reversing from slow naturally skips the center.
  • Use a dummy head for deletion problems to handle removing the original head.
  • For detect_cycle_start, only run entry-finding if the meeting happened (use while/else as above).

• Complexity summary:

  • Cycle detection, cycle entry, middle, palindrome, remove-nth: O(n) time, O(1) space.
  • Array/number variants (287, 202): O(n) time / O(1) space; number transform steps are cheap.

✅ Sliding Window (fixed size)

Summary (Key points):

• Maintain a window of exact length k; slide it by adding the right element and removing the left.
• Keep running aggregates (sum, counts) in O(1) per step.
• Typical time O(n), space O(1) to O(Σ) where Σ is alphabet size if counting chars.

Details

• Concept recap:

  • Use indices l and r; r advances each step.
  • Add a[r] into the window; if window size exceeds k, remove a[l] and l += 1.
  • When window size == k, evaluate/update the answer.

• Generic template:

  def fixed_window(a, k):
      n = len(a)
      cur = 0
      best = float("-inf")
      l = 0
      for r, x in enumerate(a):
          cur += x
          if r - l + 1 > k:
              cur -= a[l]
              l += 1
          if r - l + 1 == k:
              best = max(best, cur)
      return best

• Case 1: Maximum Average Subarray I — max average of size k

  • Keep sum of last k; update max.
  • Time: O(n), Space: O(1).

  def find_max_average(nums, k):
      cur = sum(nums[:k])
      best = cur
      for i in range(k, len(nums)):
          cur += nums[i] - nums[i - k]
          best = max(best, cur)
      return best / k

• Case 2: Maximum Number of Vowels in a Substring of Given Length

  • Maintain count of vowels in the current window of size k.
  • Time: O(n), Space: O(1).

  def max_vowels(s, k):
      vowels = set("aeiou")
      cnt = sum(c in vowels for c in s[:k])
      best = cnt
      for i in range(k, len(s)):
          cnt += (s[i] in vowels) - (s[i - k] in vowels)
          if cnt > best:
              best = cnt
      return best

• Case 3: Find All Anagrams in a String

  • Fixed-size window len(p); track char frequencies and a “matches needed” counter.
  • Time: O(n + Σ), Space: O(Σ) where Σ ≤ 26 for lowercase.

  from collections import Counter
  
  def find_anagrams(s: str, p: str):
      if len(p) > len(s): return []
      need = Counter(p)
      k = len(p)
  
      # prime first window
      win = Counter(s[:k])
      matches = sum(1 for ch in need if win[ch] == need[ch])
      out = []
      if matches == len(need):
          out.append(0)
  
      for r in range(k, len(s)):
          l = r - k
          add, rem = s[r], s[l]
          # update for removing rem
          if win[rem] == need.get(rem, 0):
              matches -= 1
          win[rem] -= 1
          if win[rem] == need.get(rem, 0):
              matches += 1
          # update for adding add
          if win[add] == need.get(add, 0):
              matches -= 1
          win[add] += 1
          if win[add] == need.get(add, 0):
              matches += 1
  
          if matches == len(need):
              out.append(l + 1)
      return out

• Case 4: Permutation in String

  • Same as anagram detection; return True on first match.
  • Time: O(n + Σ), Space: O(Σ).

  from collections import Counter
  
  def check_inclusion(p: str, s: str) -> bool:
      if len(p) > len(s): return False
      need = Counter(p)
      k = len(p)
      win = Counter(s[:k])
      if all(win[ch] == need[ch] for ch in need):
          return True
      for r in range(k, len(s)):
          l = r - k
          win[s[l]] -= 1
          win[s[r]] += 1
          if all(win[ch] == need[ch] for ch in need):
              return True
      return False

• Case 5: Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

  • Count windows with sum ≥ k*threshold.
  • Time: O(n), Space: O(1).

  def num_of_subarrays(arr, k, threshold):
      target = k * threshold
      cur = sum(arr[:k])
      ans = 1 if cur >= target else 0
      for i in range(k, len(arr)):
          cur += arr[i] - arr[i - k]
          if cur >= target:
              ans += 1
      return ans

• Pitfalls:

  • Off-by-one on window size checks; ensure r - l + 1 == k before evaluating.
  • For frequency windows, prefer arrays of size 26 for lowercase to reduce overhead.

• Complexity summary:

  • O(n) time, O(1) to O(Σ) extra space depending on what you track.

✅ Sliding Window (variable size)

Summary (Key points):

• Expand right pointer; while constraint is violated, shrink left until valid.
• Maintain counts/sums to test constraints quickly.
• Typical goals: longest valid window, shortest window reaching a target, counting windows.
• Time O(n) average/amortized, space O(Σ) for maps.

Details

• Concept recap:

  • r increases every step; add a[r] to state.
  • While not valid, remove a[l] from state and l += 1.
  • Update the answer whenever the window is valid (max/min length, counts, etc.).

• Generic template:

  def variable_window(a, is_valid_update, is_valid_check):
      l = 0
      best = 0
      state = ...  # counters, sums, etc.
      for r, x in enumerate(a):
          # add x to state
          is_valid_update(state, x, +1)
          # shrink while invalid
          while not is_valid_check(state):
              is_valid_update(state, a[l], -1)
              l += 1
          # record answer (e.g., length)
          best = max(best, r - l + 1)
      return best

• Case 1: Longest Substring Without Repeating Characters

  • Maintain counts; shrink until no char count > 1.
  • Time: O(n), Space: O(Σ).

  def length_of_longest_substring(s: str) -> int:
      from collections import defaultdict
      count = defaultdict(int)
      l = 0
      best = 0
      for r, ch in enumerate(s):
          count[ch] += 1
          while count[ch] > 1:
              count[s[l]] -= 1
              l += 1
          best = max(best, r - l + 1)
      return best

• Case 2: Minimum Size Subarray Sum — positive integers

  • Expand sum; shrink while sum ≥ target; track minimal length.
  • Time: O(n), Space: O(1).

  def min_sub_array_len(target: int, nums) -> int:
      l = 0
      cur = 0
      best = float("inf")
      for r, x in enumerate(nums):
          cur += x
          while cur >= target:
              best = min(best, r - l + 1)
              cur -= nums[l]
              l += 1
      return 0 if best == float("inf") else best

• Case 3: Fruit Into Baskets — at most 2 distinct

  • Maintain freq map; shrink if len(map) > 2; maximize length.
  • Time: O(n), Space: O(Σ).

  from collections import defaultdict
  
  def total_fruit(fruits) -> int:
      count = defaultdict(int)
      l = 0
      best = 0
      for r, x in enumerate(fruits):
          count[x] += 1
          while len(count) > 2:
              count[fruits[l]] -= 1
              if count[fruits[l]] == 0:
                  del count[fruits[l]]
              l += 1
          best = max(best, r - l + 1)
      return best

• Case 4: Longest Repeating Character Replacement

  • Window valid if (window_length - max_count) ≤ k; track max_count of any char.
  • Time: O(n), Space: O(Σ).

  from collections import defaultdict
  
  def character_replacement(s: str, k: int) -> int:
      count = defaultdict(int)
      max_count = 0
      l = 0
      best = 0
      for r, ch in enumerate(s):
          count[ch] += 1
          max_count = max(max_count, count[ch])
          while (r - l + 1) - max_count > k:
              count[s[l]] -= 1
              l += 1
          best = max(best, r - l + 1)
      return best

• Case 5: Max Consecutive Ones III — flip at most k zeros

  • Equivalent to window with at most k zeros.
  • Time: O(n), Space: O(1).

  def longest_ones(nums, k: int) -> int:
      zeros = 0
      l = 0
      best = 0
      for r, x in enumerate(nums):
          if x == 0:
              zeros += 1
          while zeros > k:
              if nums[l] == 0:
                  zeros -= 1
              l += 1
          best = max(best, r - l + 1)
      return best

• Case 6: Subarrays with K Different Integers

  • Count subarrays with exactly K distinct = atMost(K) − atMost(K−1).
  • Time: O(n), Space: O(Σ).

  from collections import defaultdict
  
  def subarraysWithKDistinct(nums, K: int) -> int:
      def at_most(k: int) -> int:
          count = defaultdict(int)
          l = 0
          res = 0
          distinct = 0
          for r, x in enumerate(nums):
              if count[x] == 0:
                  distinct += 1
              count[x] += 1
              while distinct > k:
                  count[nums[l]] -= 1
                  if count[nums[l]] == 0:
                      distinct -= 1
                  l += 1
              res += r - l + 1
          return res
      return at_most(K) - at_most(K - 1)

• Case 7: Binary Subarrays With Sum

  • For binary array, subarrays with sum S = atMost(S) − atMost(S−1) using sum-based window.
  • Time: O(n), Space: O(1).

  def num_subarrays_with_sum(nums, goal: int) -> int:
      def at_most(S: int) -> int:
          if S < 0: return 0
          l = 0
          cur = 0
          res = 0
          for r, x in enumerate(nums):
              cur += x
              while cur > S:
                  cur -= nums[l]
                  l += 1
              res += r - l + 1
          return res
      return at_most(goal) - at_most(goal - 1)

• Pitfalls and tips:

  • Only works as-is for non-negative numbers when using sum constraints (e.g., 209, 930). With negatives, sliding window may fail; use prefix sums or other techniques.
  • For character problems, maintain frequency counts and adjust while condition is violated.
  • For 424, keep max_count as the historical maximum within the window; you don’t need to decrease it when shrinking.

• Complexity summary:

  • Typically O(n) time and O(Σ) extra space per problem.
  • Counting variants often use “at most K” helper and subtraction for “exactly K”.

[tpemeja]

To find start circle :

https://leetcode.com/problems/linked-list-cycle-ii/solutions/6750409/video-3-solutions-two-pointer-set-and-recursion/

Since FAST = 2(SLOW)

2(A + B) = A + B + C + B => A = C

So just need to make one reset and both same speed, and then both will arrive at A at the same time since when meet B and B + C = A again for the one in the loop.