Opposite Direction Pointers

What is this?

Picture two people walking toward each other from opposite ends of a hallway. At every step you look at the pair where they stand and decide which person should take the next step inward. Because one marker always advances and they never turn back, the gap between them closes steadily until they meet, letting you solve the problem in a single sweep instead of comparing every pair.

💡 Fun fact: This is exactly how the classic "Container With Most Water" puzzle is solved. Always moving the shorter wall inward guarantees you never miss the best answer, even though you skip looking at most of the possible pairs.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Put one pointer at each end of the array and walk them toward each other. At every step you ask "which end is spent — which one can I retire knowing I've lost nothing?" — advance that one. The window shrinks by one each step, so the whole scan is O(n) with O(1) space.

The shape of the pattern

Unlike a nested loop that re-examines pairs, opposite-direction pointers discard a candidate permanently on every move. The entire correctness argument lives in one sentence: why is it safe to advance this pointer instead of the other? Nail that discard rule and the code is four lines.

When to reach for it

• The array is sorted, or the answer depends on both ends (extremes).
• You're optimizing a quantity defined by a pair (max area, closest sum, a merged ordering).
• You can argue that moving one end can never improve the result, so it's safe to drop.

If the input isn't ordered but the strategy needs order (greedy from both ends), sort first — that's the O(n log n) setup behind problems like Bag of Tokens.

The three problems in this chapter

Container With Most Water — the discard rule, in its purest form

Two walls hold water up to the shorter of them, over the width between them. Start wide (L=0, R=n-1) and always move the shorter wall inward: the strong side is never the constraint, so retiring the weak side is the only move that can find something better.
→ area = min(h[L], h[R]) × (R − L); O(n) / O(1).

Squares of a Sorted Array — the extremes hold the biggest values

After squaring a sorted (possibly negative) array, the largest squares sit at the two ends (most-negative vs most-positive). Compare the two ends, drop the bigger square into the result from the back, and step that end inward. A merge of two sorted runs without a sort.
→ O(n) / O(n) (output array).

Bag of Tokens — sort, then play both ends

Sort the tokens. Buy a point with the cheapest token (left) when you can afford it; when stuck, sell a point by cashing in the priciest token (right) to refuel power. Track the high-water score.
→ O(n log n) to sort, then an O(n) two-pointer sweep.

The cross-cutting skill: the discard argument

Every opposite-end solution is "evaluate the pair, then move the spent end." If you can't say why the moved end is spent, you don't yet have a correct solution — you have a guess.

📓 Draw it yourself

1. The inward walk. Draw a row of bars, L at the left, R at the right, arrows pointing inward, and write your discard rule above the picture. Re-draw it for each of the three problems — the rule changes, the skeleton doesn't.
2. Fill-from-the-back. For Squares, draw the input with L/R and a separate result row being filled right to left. Seeing the result grow backward is the whole trick.

Snap photos and embed them with the /host-diagrams skill.

Complexity at a glance

Key takeaways

• Start at both ends, walk inward. The window shrinks by one each step → O(n), O(1).
• The discard rule is everything. Decide which end is "spent" and prove moving it loses nothing.
• Sortedness powers the pattern — and when a greedy needs order, sorting first (O(n log n)) is a legitimate setup, not a failure.
• Why interviewers like it: it exposes whether you can replace a nested loop with a justified linear sweep — and whether you can argue correctness, not just code it.

Order: Container With Most Water → Squares of a Sorted Array → Bag of Tokens. The discard rule gets subtler each step.