Converging Pointers : The Correctness Proof

The two-sum-on-sorted setup

Given a sorted array a and a target T, find indices (i, j) with a[i] + a[j] == T and i < j. The brute force is O(n²); the converging-pointers algorithm is O(n) and uses no extra memory.

def two_sum_sorted(a, T):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == T: return (i, j)
        if s < T:  i += 1                               # need a larger sum
        else:      j -= 1                               # need a smaller sum
    return None

The correctness argument

We claim: at every iteration, if the answer pair exists in the array, it lies within [i, j]. Therefore when the algorithm terminates without finding it (i.e. i ≥ j), no answer exists.

Proof by induction on iterations. Base case: at the start, (i, j) = (0, n−1), so the candidate range is the entire array. Any answer is in [i, j].

Inductive step. Assume the invariant holds before iteration k. We show it holds after.

Three cases at iteration k:

• If a[i] + a[j] == T, we return, and we're done.
• If a[i] + a[j] < T, the sum is too small. Since the array is sorted, every pair (i, k) for k < j has a[k] ≤ a[j], so a[i] + a[k] ≤ a[i] + a[j] < T. None of them can be the answer. Therefore the answer (if any) does not involve index i as the smaller endpoint paired with anything ≤ j. So advancing i to i + 1 doesn't lose the answer. The new range [i + 1, j] still contains the answer.
• If a[i] + a[j] > T, symmetric argument: every pair (k, j) for k > i has a[k] ≥ a[i], so all such pairs sum to ≥ a[i] + a[j] > T. The answer does not involve j; decrementing j preserves the invariant.

Therefore the invariant holds at the next iteration. The algorithm either finds the answer or exits the loop with the candidate range empty, meaning no answer existed.

Why it terminates

Each iteration either returns or strictly advances one pointer toward the other. The gap j - i strictly decreases. Once i ≥ j, the loop exits. Total iterations bounded by n; total work bounded by O(n).

Extending to 3-Sum

"Find triplets that sum to zero." Sort the array. For each index i, run two-sum on the suffix [i+1..n) for target −a[i]. The outer loop is O(n); the inner two-sum is O(n); total O(n²).

def three_sum(nums):
    nums.sort()
    out = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue     # skip duplicates
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:  l += 1
            elif s > 0: r -= 1
            else:
                out.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
    return out

The duplicate-skipping logic deserves attention. Without it, the same triplet is found multiple times whenever any element repeats. The technique: after recording a hit, advance both pointers past any further occurrences of their values.

Container with most water

"Given heights, find two indices whose rectangle (width × min height) has maximum area."

Brute force is O(n²) over all pairs. Converging pointers is O(n). The argument is more subtle than two-sum: at each step we advance the shorter side, because shrinking the width while keeping the shorter height is guaranteed not to improve the area.

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

Why advancing the shorter side is safe: the current pair has area min(h[i], h[j]) × (j - i). If we kept the shorter side and shrank the width by advancing the longer side, the new area would be at most min(h[i], h[j]) × (new_width < old_width), which is strictly smaller. So that direction can't improve. The only direction that might improve is advancing the shorter side, where the height could grow.

Trapping rain water

"Given heights, compute total water trapped between bars." Classic O(n²) brute force; O(n) with two pointers + running maxima.

def trap(heights):
    if not heights: return 0
    i, j = 0, len(heights) - 1
    left_max = right_max = total = 0
    while i < j:
        if heights[i] < heights[j]:
            left_max = max(left_max, heights[i])
            total += left_max - heights[i]
            i += 1
        else:
            right_max = max(right_max, heights[j])
            total += right_max - heights[j]
            j -= 1
    return total

The insight: at each step, the side with the smaller current height has its trap-amount fully determined by its running max (because the other side's max is at least that high and can act as the bound). So we can fix one side's contribution to the answer and advance.

Recognising the shape

Reach for converging pointers when:

• The input is sorted (or can be sorted cheaply).
• The question asks about pairs (or generalises to triplets via outer loop).
• The decision to advance has a monotone justification: moving in the wrong direction can be ruled out by a sortedness argument.

If sortedness fails or the decision isn't monotone, this technique doesn't apply. Fall back to hash-map seen-so-far for unsorted pair problems, or to sliding window for contiguous-subarray problems.

Where beginners go wrong

• Trying to apply the technique on unsorted input. The correctness argument depends on sortedness. Sort first or use a different algorithm.
• Advancing both pointers each iteration. Discards pairs that might have been the answer. Move exactly one per iteration.
• Forgetting duplicate-skip in 3-Sum. Without it, you emit the same triplet multiple times whenever values repeat.
• Confusing "shorter side" with "left side" in container. The advance rule depends on which height is currently smaller, not on a fixed pointer.
• Reading the proof and then implementing without checking the boundary. Tests with single-element arrays and length-2 arrays are quick to write; they catch most off-by-one bugs.

What to read next

The Sliding Window in Depth piece covers the close cousin where both pointers move forward. The Floyd's Tortoise & Hare deep-dive covers fast/slow pointers: pointers at different speeds rather than at different positions.