TechPrep
Arrays and stringsReadLabPracticeCheck

Two pointers

Two indices that move toward each other (or together) so each step safely discards part of the search.

Container With Most Water. height[i] is a vertical wall at x = i. Choose two walls that, with the x-axis, hold the most water. Return the area.

Signals that point here

The idea

Start with the widest container. Width can only shrink from here, so the only way to do better is a taller short wall. Moving the taller wall inward can never raise the minimum, so every container it would form is no better: discard them by moving the shorter wall.

That argument is the whole pattern: each move must be justified by a sentence that says why the discarded options cannot win. Say it out loud; it is what separates a pattern-matcher from someone who understands the proof.

def max_area(height: list[int]) -> int:
    left, right, best = 0, len(height) - 1, 0
    while left < right:
        width = right - left
        best = max(best, width * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1                  # the short wall limits every narrower box
        else:
            right -= 1
    return best

Complexity

O(n) time, O(1) space: each step moves one pointer, and they meet after n - 1 steps.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Given a sorted array, return whether any two numbers sum to k in O(1) extra space.
  2. Return all unique triplets that sum to zero.
  3. Move all zeros to the end of an array in place, keeping the order of the other elements.

Check yourself

Why is it safe to move the shorter wall?

Every narrower container that keeps the shorter wall has a smaller width and a height capped by that same wall, so none can beat the current one.

What usually has to be true of the input for opposite-end pointers?

Sorted order (or a monotone property) so a comparison tells you which side to discard.

Saved in this browser.