Opposite-Ends Pointers

n vertical lines, pick two to form a water container — maximize min(height[l], height[r]) × width. There are ~n²/2 pairs. But start at the widest pair and ask one question: which line is the bottleneck? Move only that one, and you can prove you never skip the best container — O(n²) pairs inspected in a single O(n) walk. The whole flavor rests on one promise: moving a pointer in the right direction can never skip a valid answer.

The most common two-pointer flavor. l starts at 0, r starts at n - 1, and they walk toward each other based on a comparison. The whole technique is built on a single idea:

Moving one pointer in a known direction can’t skip a valid answer.

When that’s true, you can collapse a O(n²) “for every pair” brute force into a O(n) single pass.

The template

l = 0
r = n - 1
while l < r:
    compare arr[l] and arr[r]
    if (some condition):
        record the answer (optionally)
        l += 1 OR r -= 1 OR both
    elif (need a larger value):
        l += 1
    else:  # need a smaller value
        r -= 1

Three things vary problem-to-problem:

The comparison — sum, equality, character match.
When and what to record — return immediately, accumulate a max, push to an output list.
The movement rule — which pointer moves based on which condition.

The rest is the same skeleton.

Worked example 1: Two Sum II (sorted)

Given a 1-indexed sorted array numbers and target t, find the two 1-indexed positions i < j with numbers[i] + numbers[j] = t. There is exactly one solution.

Time: O(n). Space: O(1).

The convergence argument:

If numbers[l] + numbers[r] < t: any pair starting at l with a smaller right value (< r) would be even smaller. So no answer uses l — advance it.
If numbers[l] + numbers[r] > t: any pair ending at r with a larger left value would be even bigger. So no answer uses r — retreat it.

Each move discards a row OR a column of the implicit n × n pair grid. After at most 2n − 1 moves, all valid pairs have been considered or excluded.

Worked example 2: Valid Palindrome

Given a string s, return true if it’s a palindrome after lowercasing and removing non-alphanumerics.

Time: O(n). Space: O(1) — no copy of the filtered string.

The inner while loops handle the “skip junk characters” requirement without breaking the linear bound: each character is visited at most once by l and at most once by r.

Worked example 3: Container With Most Water

You’re given n non-negative integers height[0..n-1] representing the heights of vertical lines. Find two lines that together with the x-axis form a container holding the most water.

Brute force: for every pair, area = min(height[l], height[r]) × (r − l). O(n²).

Predict first

You're at (l, r) with height[l] = 3 and height[r] = 8. Width can only shrink as pointers converge. To have any chance at a bigger area than the current one, which line MUST you move — the short one (3) or the tall one (8)?

Two-pointer: start l, r at the ends. The area at any step is min(h[l], h[r]) × (r − l). To beat the current area, we’d need to either move past the shorter line (since it’s the bottleneck) or hope the wider container has both lines taller. Moving the shorter line inward is the only direction that could increase the area — moving the taller line only ever decreases width without raising the bottleneck.

Time: O(n). Space: O(1).

Why “move the shorter line” is correct: the area is bottlenecked by the shorter line. If we moved the taller one, the new bottleneck is at best the same (and could be smaller); the width is smaller; the area can only go down. So any improvement must involve moving the shorter line. We can safely skip every pair whose taller side is the current one. That’s the convergence argument for this problem.

Recall the one decision that drives the whole O(n) walk — which pointer steps inward:

python · fill in the blanks0/2 hints

def max_area(height):
  l, r = 0, len(height) - 1
  best = 0
  while l < r:
      best = max(best, min(height[l], height[r]) * (r - l))
      # ??? move the bottleneck (shorter) line inward
      # ??? move the bottleneck (shorter) line inward
  return best

Worked example 4: Three Sum (reduction)

Given an integer array nums, return all triplets [a, b, c] with a + b + c = 0 and no duplicate triplets.

The trick: sort, fix the first element, run two-pointer on the rest. This reduces 3Sum to “find pairs summing to −nums[i]”.

Time: O(n²). Space: O(1) extra (the output doesn’t count).

⚠️

Duplicate handling is the hardest part of 3Sum. Three places need it:

After fixing i, skip the next i if nums[i] == nums[i - 1] (same first element gives identical triplets).
After finding a valid triplet, advance l past all equal values.
After finding a valid triplet, retreat r past all equal values.

Skip any of the three and you’ll emit duplicates. Skip both 2 and 3 and you’ll emit the same triplet n times for arrays with many zeros.

A summary table

Problem	When to move `l` (forward)	When to move `r` (backward)
Two Sum II (sorted)	`sum < target`	`sum > target`
Valid Palindrome	always after match; skip non-alnum	always after match; skip non-alnum
Container With Most Water	`height[l] < height[r]`	`height[l] >= height[r]`
3Sum (inner)	`s < target`	`s > target`
Trapping Rain Water (preview)	`height[l] < height[r]`	`height[l] >= height[r]`

Notice how often the rule is the same shape: “move the side that’s smaller / weaker / not-yet-satisfied”. That’s the heuristic for almost every new opposite-ends problem.

Quick check

In Container With Most Water, you compute the area at (l, r). Why is it always correct to move the SHORTER line inward?

In Three Sum, why do we sort first?

A common Three Sum bug: emitting [-1, 0, 1] twice for input [-1, -1, 0, 1, 1]. What's missing?

Opposite-ends pointers converge toward each other on sorted or symmetric data. Next, the mirror image: same-direction pointers — both walk forward, one reading and one writing, for in-place transforms that need O(1) extra space.

Introduction Same-Direction Pointers

Finished this page?