👆 Two Pointers

The Pincer Movement Analogy

Imagine searching for a book on a shelf:

Naive approach: Start from the left, check every book. O(n).

Two pointers approach: Start from BOTH ends simultaneously. If the book is on the right half, the left pointer tells you immediately. O(n/2) comparisons.

Two pointers uses two position markers that move through data, often toward each other or in the same direction.

The Core Patterns

Pattern 1: Opposite Direction (Converging)

Pointers start at opposite ends and move toward each other:

Array: [1, 2, 3, 4, 5, 6, 7, 8]
        L →             ← R

Left pointer moves right
Right pointer moves left
They meet in the middle

Use for: Finding pairs, palindrome check, container problems.

Pattern 2: Same Direction (Fast/Slow)

Both pointers start at the same end, move at different speeds:

Array: [1, 2, 3, 4, 5, 6, 7, 8]
        S →
        F →→

Slow pointer: 1 step at a time
Fast pointer: 2 steps (or conditionally)

Use for: Removing duplicates, cycle detection, partitioning.

Classic Problems Explained

1. Two Sum (Sorted Array)

Problem: Find two numbers that add up to a target sum.

Array: [2, 7, 11, 15], Target: 9

Step 1: L=2, R=15 → sum=17 > 9, move R left
Step 2: L=2, R=11 → sum=13 > 9, move R left
Step 3: L=2, R=7  → sum=9 = target! ✓

Answer: indices [0, 1]

Logic:

• Sum too big? Move right pointer left (decrease sum)
• Sum too small? Move left pointer right (increase sum)

2. Container With Most Water

Problem: Find two lines that form a container holding the most water.

Heights: [1, 8, 6, 2, 5, 4, 8, 3, 7]
          L →                   ← R

Water = min(L, R) × width

Start: min(1, 7) × 8 = 8
Move L (smaller one) to find potentially taller line
Next:  min(8, 7) × 7 = 49
...

Logic: Typically move the pointer pointing to the shorter line.

3. Valid Palindrome

Problem: Check if a string reads the same forwards and backwards.

String: "A man, a plan, a canal: Panama"
Clean:  "amanaplanacanalpanama"

L → a                           a ← R  → Match!
    m                         m        → Match!
    a                       a          → Match!
    ...continue until L >= R...

All match = Valid palindrome!

4. Remove Duplicates (In-Place)

Problem: Remove duplicates from sorted array, return new length.

Array: [1, 1, 2, 2, 3]
        S
        F

Slow marks where to write
Fast scans for unique elements

F finds 1 (=S), skip
F finds 2 (≠S), write to S+1, move S
F finds 2 (=S), skip
F finds 3 (≠S), write to S+1, move S

Result: [1, 2, 3, _, _], length = 3

5. Move Zeroes

Problem: Move all zeroes to end while maintaining order of non-zeroes.

Array: [0, 1, 0, 3, 12]

Slow = write position for non-zeros
Fast = scanner

F finds 1 → write at S, S++
F finds 3 → write at S, S++
F finds 12 → write at S, S++
Fill rest with zeros

Result: [1, 3, 12, 0, 0]

When to Use Two Pointers

Quick Recognition

Keywords that suggest two pointers:
- "Sorted array" + "find pair"
- "In-place" modification
- "Palindrome"
- "Container" or "trapped water"
- "Remove duplicates"
- "Cycle detection"

Two Pointers vs Other Techniques

Key Difference from Sliding Window

Two Pointers: Pointers can be ANYWHERE
  [  L        R  ]   (not necessarily adjacent)

Sliding Window: Pointers define CONTIGUOUS range
  [L R]              (window of consecutive elements)

Time and Space Complexity

Two pointers typically achieve:

Time:  O(n) - each pointer traverses array at most once
Space: O(1) - just two variables

Compare to brute force:
  Two Sum without sorting: O(n²) with nested loops
  Two Sum with two pointers: O(n) after O(n log n) sort

Common Mistakes

1. Forgetting to Sort

Two pointers on unsorted data gives wrong results for many problems!

2. Off-by-One at Boundaries

Wrong: while left < right (misses when left == right)
Right: Depends on problem! Know when to stop.

3. Moving Wrong Pointer

In converging patterns, usually move the pointer that helps approach the target.

4. Not Handling Duplicates

Many problems have tricky duplicate cases. Handle them explicitly.

FAQ

Q: Does the array need to be sorted?

For opposite-direction patterns (like Two Sum), usually YES. For same-direction patterns (like remove duplicates), it depends on the problem.

Q: Two pointers vs sliding window?

Two pointers: pairs, palindromes, non-contiguous elements. Sliding window: contiguous subarrays with size/sum constraints.

Q: Can I use two pointers on linked lists?

Yes! Fast/slow pointers are common for cycle detection and finding the middle.

Q: What if I need to find all pairs, not just one?

Modify the algorithm to continue after finding each pair instead of returning immediately.

Summary

Two pointers is a technique using two position markers to efficiently solve array and string problems.

Key Takeaways:

• Opposite direction: converge from both ends
• Same direction: one pointer leads, one follows
• Usually requires sorted data (for converging pattern)
• O(n) time and O(1) space
• Common for: pairs, palindromes, in-place modifications
• Alternative to O(n²) brute force

Master two pointers - it's one of the most common interview patterns!