Opposite ends converge

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The list 1, 2, 4, 7, 11, 15, 18 is already sorted, and you want two numbers that add to 18. By hand you could try every pair, about n² ÷ 2 of them, which is 21 for 7 numbers and about 500 billion for a million. That ignores the one thing you were given for free: the order.

Think about what order tells you. If you try 1 + 18 = 19 and it is too big, you know something stronger than "that pair failed": any pair that uses 18 with a number bigger than 1 is also too big, because 1 is the smallest. So 18 can be thrown away entirely. That single observation is the whole pattern.

Build the structure, one piece at a time

The structure is just two indices, l at the left end and r at the right end. The stretch between them is the set of numbers still "alive" as possible pair members. Each step looks at one sum and kills one end:

• If nums[l] + nums[r] is too big, nothing paired with nums[r] can work, so move r one step left.
• If it is too small, nothing paired with nums[l] can work, so move l one step right.
• If it is exactly right, done.

Six sums instead of twenty-one. The same two indices, walking inward, solve "is this string a palindrome" (compare the letters at l and r, move both inward), "reverse in place" (swap, move both), and "container with most water" (the shorter wall limits the area, so move the shorter side).

Why it is correct

The invariant: if a valid pair exists, both of its members lie in the range [l, r]. At the start the range is everything, so it holds. Suppose it holds and the sum is too big, so we drop nums[r]. Could the answer have used nums[r]? Its partner would have to be in [l, r − 1], all of which are at least nums[l] because the list is sorted, so that pair's sum is at least nums[l] + nums[r] > 18. Impossible. The mirror argument covers "too small". So dropping an end never drops a member of the answer, and the invariant survives every step. When the range shrinks to a single element with no pair found, no pair exists.

sorted ⇒ nums[l] ≤ nums[i] for all i in [l, r] ⇒ nums[i] + nums[r] ≥ nums[l] + nums[r]

Why it is fast

Every step moves l right or r left by one, and they start n − 1 apart and stop when they meet. So there are at most n − 1 steps, each a single addition and comparison: O(n) time, O(1) extra memory. The quadratic pair search did about n² ÷ 2 steps; sortedness let us discard a whole row of candidates per comparison instead of one.

How to recognise it in an interview

Cues: the input is sorted (or can be sorted cheaply), you need a pair or a pair of positions, and the test is monotone: moving one end only ever makes the sum bigger or smaller. Also any "from both ends" shape: palindromes, reversing, pairing the smallest with the largest.

Say: "The array is sorted, so I will put a pointer at each end and move the one that must move, discarding a candidate per step." Two Sum II - Input Array Is Sorted is the example. Container With Most Water uses the same loop with "move the shorter wall", because the shorter wall caps the area of every container it could form with a nearer partner. Valid Palindrome compares the two ends and moves both inward, skipping non-letters.

02The idea in one line

Sorted: too small → move left up, too big → move right down.

Reach for it when: Pair sums in sorted arrays, container with most water, palindromes.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: Two Sum II on [2,7,11,15] target 18. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sorted input: start at both ends and squeeze inward
2. l on the smallest, r on the largest
3. 1 + 18 = 19 > 18: too big, move r left
4. 1 + 15 = 16 < 18: too small, move l right
5. 2 + 15 = 17 < 18: too small, move l right
6. 4 + 15 = 19 > 18: too big, move r left
7. 4 + 11 = 15 < 18: too small, move l right
8. 7 + 11 = 18 = target: found [4, 5]
9. Each step discards one end for good: O(n) time, O(1) space

04Asked at Google

11 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Two Pointers: Fix one, two-pointer the rest, Reader / writer pointers, Dutch national flag partition, Merge two sorted sequences, Two-sided max walls.