← Back to cheat sheets

Two Pointers

1. Two Pointers: Opposite Ends

Scenario: Used on a single sorted array or string.

Setup

  • left = 0
  • right = input.length - 1
  • Logic: Move pointers toward each other until they meet.
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Common Use Cases

  • Validating Palindromes: Compare s[left] and s[right], then move both inward.
  • Two Sum (Sorted): If sum > target, move right-- to decrease sum; if sum < target, move left++ to increase sum.

2. Two Pointers: Two Iterables

Scenario: Used when comparing two different arrays or strings.

Setup

  • i = 0 (for first array)
  • j = 0 (for second array)
  • Logic: Move along both simultaneously. The loop usually ends when one pointer reaches the end.
  • Time Complexity: O(n + m) (where n and m are the lengths of the inputs).
  • Space Complexity: O(1) (excluding output storage).

Common Use Cases

  • Merging Sorted Arrays: Compare arr1[i] and arr2[j], add the smaller to the result, and increment that specific pointer.
  • Subsequence Check: Move the “main” string pointer every time, but only move the “subsequence” pointer when a match is found.

Key Takeaways

  • Efficiency: This technique often reduces brute-force solutions (nested loops) to O(n) linear time.
  • Exhaustion: For the “Two Iterables” method, remember to check if one array still has remaining elements after the main loop finishes.
  • Flexibility: While these are the “standard” patterns, pointers can start at the same index, different indices, or even move at different speeds (Slow/Fast pointers).