02 — Two Pointers

Neetcode Week 2a. Two pointers turns O(n²) brute force into O(n) by walking through the array with two indices that move based on a condition.

The core idea
Variant A — Opposing pointers (sorted array)
Variant B — Same-direction (slow/fast)
Variant C — Partitioning (Dutch flag)
When NOT to use two pointers
Walked-through problems
Pitfalls
Practice list

1. The core idea

You have one input (often sorted). Brute force tries all O(n²) pairs. Two pointers makes a smarter walk:

[1, 2, 4, 7, 11, 15]              target = 9
 ↑                ↑
 l                r        sum = 1 + 15 = 16 > 9 → r--

[1, 2, 4, 7, 11, 15]
 ↑            ↑
 l            r            sum = 1 + 11 = 12 > 9 → r--

[1, 2, 4, 7, 11, 15]
 ↑       ↑
 l       r                 sum = 1 + 7  = 8  < 9 → l++

[1, 2, 4, 7, 11, 15]
    ↑    ↑
    l    r                 sum = 2 + 7  = 9  ✓

Why O(n)? Each pointer only moves forward (or only backward). Across the whole array, each pointer makes at most n moves → O(n) total.

The trick is in the invariant — a property that holds true between iterations, letting you decide which pointer to move with O(1) thinking.

2. Variant A — Opposing pointers

Pointers start at both ends and move toward each other. Almost always requires the array to be sorted (or have some monotonic property).

Template

def opposing(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        # examine arr[l] and arr[r]
        if condition_to_move_left:
            l += 1
        else:
            r -= 1
    return result

When to use

"Find pair / triplet that sums to X in sorted array"
"Most water container" — area = min(left, right) × width
"Palindrome check"
"Reverse array in place"

Two Sum II (sorted array)

def two_sum_sorted(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l + 1, r + 1]    # 1-indexed per problem
        elif s < target:
            l += 1                   # need larger sum → move left up
        else:
            r -= 1                   # need smaller sum → move right down
    return [-1, -1]

Why moving the right pointer when sum > target is correct:

Array is sorted. Any pair (l, k) for k < r has nums[k] <= nums[r] → nums[l] + nums[k] <= nums[l] + nums[r].
We already know nums[l] + nums[r] > target, so any (l, k) with smaller k has even bigger or equal sum if we only moved l up. Actually we want to decrease the sum, so r-- is correct.
The invariant: "every valid pair, if it exists, lies within [l, r]."

3Sum (the canonical extension)

Find all unique triplets that sum to 0.

Approach: sort. Fix the first element, then two-pointer the remaining two.

def three_sum(nums):
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:                          # all later are >= nums[i] > 0
            break
        if i > 0 and nums[i] == nums[i-1]:       # skip duplicate "first" elements
            continue
        l, r = i + 1, n - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l-1]:    # skip dup l
                    l += 1
                while l < r and nums[r] == nums[r+1]:    # skip dup r
                    r -= 1
            elif s < 0:
                l += 1
            else:
                r -= 1
    return res

Complexity: O(n²) — outer loop n, inner two-pointer n. Space: O(1) extra (excluding output).

The dedup logic is the only tricky part. Read it 3 times and trace [-1, -1, 0, 1, 2].

Container With Most Water (visual proof)

heights = [1,8,6,2,5,4,8,3,7]. Pick two lines forming the largest rectangle.

8 |  ▓                 ▓
7 |                          ▓
6 |     ▓
5 |           ▓
4 |              ▓
3 |                       ▓
2 |        ▓
1 |  ▓
0 +-------------------------------
   0  1  2  3  4  5  6  7  8

Area between i=1 (height 8) and i=8 (height 7):
   width = 7, min_height = 7  →  area = 49

def max_area(heights):
    l, r = 0, len(heights) - 1
    best = 0
    while l < r:
        h = min(heights[l], heights[r])
        best = max(best, h * (r - l))
        if heights[l] < heights[r]:
            l += 1                      # short side limits area; move it
        else:
            r -= 1
    return best

Why move the shorter side? The area is min(L, R) * width. If we move the taller pointer inward, width shrinks but min_height can't increase (still bounded by short side). So we'd only get smaller. Moving the shorter side is the only chance to increase.

This is a proof-style argument worth saying out loud in interviews.

3. Variant B — Same-direction (slow/fast)

Both pointers start at the left. The fast one explores; the slow one writes. Common use: in-place modification of an array.

Template

def same_direction(arr):
    slow = 0                            # write head
    for fast in range(len(arr)):        # read head
        if keep_arr_at(fast):
            arr[slow] = arr[fast]
            slow += 1
    return slow                         # number of kept elements

Remove Duplicates from Sorted Array

def remove_duplicates(nums):
    if not nums: return 0
    slow = 0                            # last unique written
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1                     # length of unique prefix

Trace [1,1,2,3,3,4]:

slow=0 (1), fast=1: 1==1 → skip
slow=0 (1), fast=2: 2!=1 → slow=1, nums=[1,2,2,3,3,4]
slow=1 (2), fast=3: 3!=2 → slow=2, nums=[1,2,3,3,3,4]
slow=2 (3), fast=4: 3==3 → skip
slow=2 (3), fast=5: 4!=3 → slow=3, nums=[1,2,3,4,3,4]
return 4    (prefix [1,2,3,4] is unique)

Move Zeroes (keep relative order)

def move_zeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Swap variant ensures non-zero elements stay in original relative order while zeros bubble right.

Linked-list use case

Same direction with two pointers, one moving twice as fast, is the classic cycle detection (Floyd's). Covered in 06-linked-list.md.

4. Variant C — Partitioning

Three pointers (or two with a tracking pointer) splitting an array into regions.

Dutch National Flag (Sort Colors)

Sort [2, 0, 1, 1, 2, 0, 1] in place with values only 0, 1, 2 — single pass.

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:                                    # 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # don't increment mid — the swapped-in value is unexamined
    return nums

Invariants during the loop:

nums[0..low-1] are all 0 (settled)
nums[low..mid-1] are all 1 (settled)
nums[mid..high] are unexamined
nums[high+1..] are all 2 (settled)

When mid > high, every cell is settled.

Why "don't increment mid when swapping with high"?

Because the value swapped into mid came from high, which was unexamined. We need to examine it next iteration. The value swapped into low came from mid (already known to be 0), so we can safely advance.

5. When NOT to use two pointers

Unsorted array, opposing-pointer style. The invariant relies on monotonicity. If [3, 1, 5, 2] and target = 4, opposing pointers won't work — sort first.
Need to find the actual subarray (not just count) and order matters in different way. Sometimes sliding window is more natural — see 03-sliding-window.md.
Multiple unrelated criteria. If you need a (min, max, sum, count) all simultaneously, you might need DP or segment tree.

6. Walked-through problems

Valid Palindrome (Easy)

Treat alphanumeric only, case-insensitive.

def is_palindrome(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].lower() != s[r].lower():
            return False
        l += 1
        r -= 1
    return True

Inner whiles are crucial: skip non-alphanumeric. Notice they have l < r guard to avoid running off either end.

Trapping Rain Water (Hard)

heights = [0,1,0,2,1,0,1,3,2,1,2,1] — total water trapped?

Idea: at each index i, water trapped is min(maxLeft, maxRight) - heights[i].

Brute O(n²): for each i, scan left and right for max. Two-pointer O(n): track max from each side as we walk inward.

def trap(heights):
    if not heights: return 0
    l, r = 0, len(heights) - 1
    left_max = right_max = 0
    total = 0
    while l < r:
        if heights[l] < heights[r]:
            # left side is the limiting wall
            if heights[l] >= left_max:
                left_max = heights[l]                # update wall
            else:
                total += left_max - heights[l]       # water on top of l
            l += 1
        else:
            if heights[r] >= right_max:
                right_max = heights[r]
            else:
                total += right_max - heights[r]
            r -= 1
    return total

Why it's correct: when heights[l] < heights[r], the left side is the bottleneck — even if there's a taller wall to the right, the water level above index l is bounded by left_max, NOT by anything on the right (because we know there's at least heights[r] >= heights[l] on the right). So we can compute trap-at-l using only left_max.

This is a classic case where the monotonic invariant ("the side we move always has a known wall") substitutes for a full max-array.

7. Pitfalls

`l < r` vs `l <= r`

For pair-finding: l < r (we never want l == r — that's the same element).

For binary search: l <= r typically (we're searching, not pairing). Different use case.

Boundary skip with infinite-loop risk

while l < r and not s[l].isalnum(): l += 1
while l < r and not s[r].isalnum(): r -= 1

The l < r guard is essential — without it, both whiles could each advance past the other end on a string like ",,,,".

Forgetting to skip duplicates in 3Sum

Without the dedup whiles, [0,0,0,0] produces [0,0,0] four times. Always dedup after a match.

Movement direction

The single most common bug is moving the wrong pointer. Always state the invariant: "if sum < target, the smallest possible pair with current r is too small, so we need a bigger left → l++."

Extra space

Two pointers should be O(1) extra space. If your solution feels like O(n) extra, you're probably using a hash — that's a different pattern (or 3Sum-style).

8. Practice list

#	Problem	Variant	Difficulty
125	Valid Palindrome	Opposing	Easy
167	Two Sum II	Opposing	Medium
15	3Sum	Sort + opposing	Medium
11	Container With Most Water	Opposing + greedy	Medium
42	Trapping Rain Water	Opposing + max-tracking	Hard
26	Remove Duplicates from Sorted Array	Same-direction	Easy
283	Move Zeroes	Same-direction	Easy
75	Sort Colors	Dutch flag	Medium
16	3Sum Closest	Sort + opposing	Medium
18	4Sum	2 outer + opposing	Medium

TL;DR ✅

Two pointers turns O(n²) pair-search into O(n) when input is sorted or has monotonic structure.
Three variants: opposing (sorted array, ends inward), same-direction (in-place modification), partitioning (Dutch flag).
Always state the invariant out loud to convince yourself which pointer to move.
Skip duplicates after matches in 3Sum-class problems.
Trapping Rain Water is the gold standard "why opposing pointers work" exercise.

Next: 03-sliding-window.md.

External resources

NeetCode 3Sum walkthrough: https://www.youtube.com/watch?v=jzZsG8n2R9A
NeetCode Trapping Rain Water: https://www.youtube.com/watch?v=ZI2z5pq0TqA
Visualization of two pointers: https://www.geeksforgeeks.org/two-pointers-technique/

02 — Two Pointers

Table of Contents

1. The core idea

2. Variant A — Opposing pointers

Template

When to use

Two Sum II (sorted array)

3Sum (the canonical extension)

Container With Most Water (visual proof)

3. Variant B — Same-direction (slow/fast)

Template

Remove Duplicates from Sorted Array

Move Zeroes (keep relative order)

Linked-list use case

4. Variant C — Partitioning

Dutch National Flag (Sort Colors)

Why "don't increment mid when swapping with high"?

5. When NOT to use two pointers

6. Walked-through problems

Valid Palindrome (Easy)

Trapping Rain Water (Hard)

7. Pitfalls

l < r vs l <= r

Boundary skip with infinite-loop risk

Forgetting to skip duplicates in 3Sum

Movement direction

Extra space

8. Practice list

TL;DR ✅

External resources

`l < r` vs `l <= r`