Two Pointers I — Opposite Ends

Review boundary and corrected contracts

The surviving window contains every possible solution pair, not every unexamined pair. A pointer discards only pairs proved impossible. Early return can stop before n−1 moves. The palindrome example has ASCII input semantics; Unicode case folding can expand a character.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the converging two-pointer skeleton and, more importantly, the argument for why moving one pointer safely eliminates an entire set of candidate pairs.

Series: LeetCode — From Basics to Production-Ready · Session 7 / 65 · Phase 1 · Core patterns

Why this session exists

Sorted pair sums suggest two pointers, but the sum’s elimination rule—not the cue alone—justifies the method. Palindromes and container area use different arguments.

This is the first real pattern in the series and it is a good one to start with, because it is the clearest example of the thing all patterns do: it can turn an O(n^2) search over pairs into an O(n) walk when a valid elimination proof exists.

Here is the argument in one sentence. If the array is sorted and you are looking at the pair (lo, hi), then the sum you see is the largest possible sum involving lo — because hi holds the largest remaining value. So if that sum is still too small, no pair involving lo can ever work, and you may discard lo entirely. One comparison eliminates a whole row of the pair matrix. Do it n times and you are done.

That structure — a comparison whose outcome licenses discarding a whole set of candidates — is what "monotonicity" means in practice, and it is the same reason binary search works in L13. Learn the argument here and you get several later sessions cheaper.

• Write the converging skeleton from a blank file, with the correct loop condition.

• State why moving lo when the sum is too small is safe, in one sentence.

• Explain why the loop condition is lo < hi rather than lo <= hi.

• Handle duplicate skipping correctly when the problem requires unique results.

Blank-file warm-up

Five minutes, empty file. Write lo = 0, hi = n - 1, while lo < hi and the body that follows. Then write, underneath, the discard argument: when the sum is too small, which pointer moves and what set of candidates does that eliminate?

A short skeleton is useful, but the elimination argument is what permits adaptation to a changed contract. Check both code and reasoning in a delayed retest rather than assuming a particular part is remembered.

Pattern anatomy

The shape that summons this: the input is sorted (or can be sorted without losing what you need), and you are looking for a pair, or optimising over pairs, where moving an endpoint changes the objective in a predictable direction.

The invariant: every possible solution pair not yet found lies entirely within the window [lo, hi]. Each pointer move must preserve that, which is exactly what the discard argument establishes.

def two_pointer_converge(a: list[int], target: int):
    """Nondecreasing integer list; return two distinct zero-based indices or None."""
    lo, hi = 0, len(a) - 1
    while lo < hi:                    # strict: lo == hi is a single
        s = a[lo] + a[hi]             #   element, not a pair
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1                   # need bigger: only lo can grow it
        else:
            hi -= 1                   # need smaller: only hi can shrink it
    return None
 
# WHY each move is safe (this is the whole pattern):
#
#   a[hi] is the largest value still available.
#   So a[lo] + a[hi] is the LARGEST sum involving a[lo].
#   If that is still < target, then a[lo] paired with anything
#   else available is even smaller. a[lo] is dead. Discard it.
#
#   Symmetrically, a[lo] is the smallest available value, so
#   a[lo] + a[hi] is the SMALLEST sum involving a[hi]. If that
#   already exceeds target, a[hi] is dead.
#
# Each unsuccessful iteration moves one endpoint; a hit returns immediately.
# At most max(n-1, 0) pair comparisons occur. That is the O(n) bound.

Two variations on the skeleton worth having ready.

Palindrome / mirror check: same converging walk, but the comparison is a[lo] != a[hi] rather than a sum, and the array need not be sorted — the pairing is positional rather than value-based.

Skipping duplicates for problems requiring unique output: after recording a hit, advance lo past every equal value and retreat hi past every equal value. This avoids repeated value triples; counting index pairs instead needs multiplicity accounting.

The cue

Five tells that this is the pattern:

1. Sorted input. Check whether order supports a safe move for this objective; it does for the pair-sum comparison below, not automatically for every task.
2. The input is not sorted but the answer does not depend on original positions. Then you may sort it yourself and the cue applies — this is what turns 3Sum into a two-pointer problem.
3. A pair objective with a proved endpoint bound. For sorted sums, moving left inward cannot decrease the sum and moving right inward cannot increase it. Products of signed values or differences may need different starting positions and cases; do not reuse the sum branches without a proof.
4. A palindrome, reversal, or any symmetric property. Positional pairing from the two ends, sorting irrelevant.
5. "Maximise something over a pair of indices" where the objective involves both the distance between them and their values — Container With Most Water is the archetype, and it is the one where the discard argument is genuinely subtle.

Two indices do not supply a correctness proof

For sorted pair sums, rank order supplies an elimination rule. Palindrome comparison instead uses positional symmetry; no value ordering is needed. Container area uses nonnegative heights and a bound on every narrower pair sharing the shorter endpoint. Pointer progress can establish a linear iteration count even for an incorrect algorithm. You need both safe elimination for correctness and bounded total work for complexity.

Guided solve

Valid Palindrome. Given a string, return true if it is a palindrome considering only alphanumeric characters and ignoring case.

Run L06's framework briefly. Understand: filter to alphanumeric, lowercase everything, then check that it reads the same forwards and backwards. Clarify: is the empty string a palindrome — yes, vacuously; are digits included — yes, alphanumeric; what about unicode — constraints say ASCII printable.

Match: symmetric property, so positional two pointers from the ends. Sortedness is irrelevant here; what matters is that position i from the left must match position i from the right.

The copy-based baseline is useful when O(n) extra space is acceptable:

def is_palindrome_naive(s: str) -> bool:
    t = "".join(c.lower() for c in s if c.isalnum())
    return t == t[::-1]          # correct, but O(n) EXTRA space

Under the stated ASCII contract, this builds a filtered copy and then a reversed copy, taking O(n) time and O(n) extra space. A two-ended scan removes the linear auxiliary storage:

def is_palindrome(s: str) -> bool:
    lo, hi = 0, len(s) - 1
    while lo < hi:
        while lo < hi and not s[lo].isalnum():   # skip junk from left
            lo += 1
        while lo < hi and not s[hi].isalnum():   # skip junk from right
            hi -= 1
        if s[lo].lower() != s[hi].lower():
            return False
        lo += 1
        hi -= 1
    return True

Three details worth narrating.

The inner skip loops need their own lo < hi guard. Without it, a string of pure punctuation walks lo off the end of the string and raises IndexError. This is the classic bug in this problem and it only shows on an input like ",." — which is exactly why L06's Review step insists on tracing an edge example.

The outer condition is strict. When lo == hi you are looking at the single middle character of an odd-length string, which is trivially equal to itself. Comparing it is unnecessary; once the endpoints meet or cross, the symmetric checks are complete. Strict inequality handles both parities with no special case.

Each character is visited at most once by each pointer. The inner while loops look like they might make this quadratic, but the pointers only ever move toward each other and never back, so the total work across the entire run is bounded by n. This "amortised across the whole loop, not per iteration" argument is worth stating explicitly — it is the same reasoning that makes sliding windows linear in L10, and reviewers do ask.

Cost under ASCII semantics: O(n) time, O(1) auxiliary space. The copy-based baseline has the same time class but linear extra storage; choose according to clarity and memory requirements. Neither implementation defines general Unicode normalization/grapheme semantics. Case conversion can expand a code point, so per-character endpoint comparison is not a general substitute for normalizing and comparing a whole Unicode sequence.

Solo timed

Fifteen minutes each. Before writing, state which pointer moves under which condition and why that is safe.

• Two Sum II — input is already sorted and the problem says so loudly. The only trap is the return format; read it twice.
• Container With Most Water — you always move the pointer at the shorter line. Prove why no narrower pair sharing the shorter endpoint can beat the current area before you write anything; that proof is the entire problem.
• 3Sum — sort, fix one index, then run the converging skeleton on the remainder. Both elimination and deduplication need justification. Decide your dedup strategy during Plan, not during debugging.

Common failure modes

• lo <= hi instead of lo < hi. Lets an element pair with itself, which silently produces wrong answers on inputs where an element is exactly half the target.
• Missing the guard inside the skip loops. IndexError on all-punctuation or all-duplicate inputs.
• Applying the pattern to unsorted input. The discard argument depends entirely on a[hi] being the largest remaining value. Without sortedness the whole thing is unfounded, and it will pass the sample tests by luck.
• 3Sum deduplication done by post-filtering. Collecting all triples and then deduping with a set works but is slower and is not what the pattern is for. Skip duplicates as you advance the pointers instead.
• Counting index pairs as if enumerating unique value pairs. On a hit with unequal endpoint values, count the left run length times the right run length, then skip both runs. If the endpoint values are equal, every remaining value is equal: add m(m-1)/2 for m remaining elements and finish. Advancing once per hit without this multiplicity usually undercounts.

Myth: Two pointers is just an optimisation of the nested loop — same idea, less work.

Truth: The exact-sum two-pointer loop examines at most max(n-1,0) pairs and rejects other candidates using sortedness; a brute-force search may return early but can inspect all pairs. Calling one an optimization is fine, provided the proof explains every discarded candidate.

Why: Because the code looks like a stripped-down nested loop and produces the same answers on the examples, so it reads as an optimisation rather than as a distinct claim about the input.

Test: Run the converging skeleton on an unsorted array. It will return a wrong answer on inputs where the discarded region contained the true pair — and it will still pass a handful of random tests, which is exactly what makes the mistake dangerous.

Question: Why is discarding a pointer safe, and why does that give O(n)?

Premise: The array is sorted, so a[hi] is the largest value in the unexamined window and a[lo] the smallest.

Because: sortedness is precisely the statement that position encodes rank.

Premise: Therefore a[lo] + a[hi] is the maximum achievable sum involving a[lo].

Because: no remaining partner exceeds a[hi].

Premise: So if that sum is below target, every pair containing a[lo] is below target.

Because: we already paired it with the best available partner and fell short.

Premise: Hence a[lo] can be removed from consideration entirely, not merely skipped this round.

Because: its best case has been evaluated and rejected.

Premise: Each unsuccessful comparison removes one endpoint; a successful comparison returns immediately.

Because: on an unsuccessful comparison exactly one pointer moves inward, reducing the gap by one.

Conclusion: For n>=2 the initial gap is n-1, so there are at most n-1 pair comparisons, including a possible final successful one. For n=0 or 1 there are zero comparisons: the unified bound is max(n-1,0). A hit can stop much earlier. This progress argument bounds work; sortedness separately proves correctness.

Name: Closing the accordion

Picture: Two hands on the ends of an accordion, squeezing inward. The note you hear is the current sum. Too flat, push the left hand in; too sharp, push the right. Hands only ever move toward each other, so the instrument closes in at most n squeezes.

• Neither hand ever moves back outward — that is what bounds the work.

• Which hand moves is dictated by the comparison, never by a guess.

• If the note does not change predictably when a hand moves, this is not the right instrument.

Trigger: The word 'sorted' in the constraints, or any symmetric property like palindrome or mirror.

Decision: Sort then two pointers, versus a hash map, for pair-finding on unsorted input.

Name: Sort, then converge

Gain: O(1) extra space beyond the sort, and it extends naturally to 3Sum and k-sum where the sorted order enables both the inner walk and clean deduplication.

Cost: O(n log n) time, and the original indices are destroyed unless you sort (value, index) pairs, which reintroduces O(n) space.

Pick: The answer is stated in terms of values rather than indices, or the problem is a k-sum variant needing dedup.

Name: Hash map, one pass

Gain: Expected O(n) time for suitable bounded-cost keys; values map to original indices.

Cost: O(n) storage and expected rather than guaranteed constant-time lookup; unique k-sum output needs additional multiplicity/dedup reasoning.

Pick: The problem asks for indices into the original array, or the input is already unsorted and k is exactly 2.

Verdict: Return type constrains the design but does not dictate it: sorted input can return original indices directly, and decorated sorting can retain unsorted original indices at a memory cost. Compare the invariant, mutation permission, full workspace and output contract; hashing and sorting are alternatives, not keyword rules.

Worked variant — 3Sum, with the deduplication annotated

3Sum combines a fixed first value with a sorted-suffix pair search. The function mutates its integer list by sorting and returns all unique zero-sum value triples, not all index triples. Both the suffix search and duplicate skipping require reasoning:

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()                       # O(n log n); indices are now meaningless,
    n, out = len(nums), []            #   which the problem permits (values asked for)
 
    for i in range(n - 2):
        # DEDUP 1 — the fixed element.
        # If nums[i] equals its predecessor, every triplet startable
        # here was already produced one iteration ago. Skip.
        if i > 0 and nums[i] == nums[i - 1]:
            continue
 
        # EARLY EXIT — array is sorted, so if the smallest available
        # value is already positive, no triple can sum to zero.
        if nums[i] > 0:
            break
 
        lo, hi = i + 1, n - 1         # converge over the SUFFIX only,
        while lo < hi:                #   which is why i never revisits pairs
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1               # need bigger; nums[lo] is dead (see L07 proof)
            elif s > 0:
                hi -= 1               # need smaller; nums[hi] is dead
            else:
                out.append([nums[i], nums[lo], nums[hi]])
                # DEDUP 2 — after a hit, walk BOTH pointers past their
                # equal runs. Reusing the same endpoint values could repeat
                # the triplet; skipping both is sufficient (not the only strategy).
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
    return out

DEDUP 1 skips repeated fixed values: their smaller suffixes cannot create a new value triple beyond those found for the first such fixed value. DEDUP 2 skips the matched endpoint runs. For fixed first value and a successful sum, choosing that same lower value forces the same higher value, so repeated copies would repeat the same value triple. Every remaining unequal pair is still explored or eliminated by the sum bound.

The post-hit moves make nums[lo-1] and nums[hi+1] refer to the matched values before the skips. Removing them is not a valid edit: for [-2,0,2], the unchanged hi+1 lookup can go out of bounds. It does not necessarily loop forever on all-zero input. An alternative implementation may save matched values explicitly and skip relative to those; unconditional movement of both pointers is a property of this version, not a theorem about all correct 3Sum algorithms.

The early break on nums[i] > 0 is not required for correctness but it is the kind of thing that reads as fluency. It only works because you sorted; say that out loud when you write it.

Memory hook — "sorted, squeeze, kill one"

Under pressure the skeleton survives and the justification evaporates, which is fatal because the justification is what lets you adapt. Peg it in three beats:

• Sorted for sums — check the precondition. Other two-ended tasks, such as palindrome checking, use symmetry or a different endpoint bound rather than sorting.
• Squeeze — the hands only ever move inward. lo never decreases, hi never increases. That one-directional property is the entire complexity proof.
• Make justified progress — an unsuccessful exact-sum step eliminates one endpoint; a hit returns, and 3Sum may advance both endpoints and skip runs. Name what is excluded and why.

For the direction, the peg is "too small, raise the floor; too big, lower the ceiling." lo is the floor and moving it up is the only way to increase the sum; hi is the ceiling and moving it down is the only way to decrease it. Nothing else is available, which is why the branch is never ambiguous.

What reviewers actually ask

This family is a screening staple because it is quick to state, has an obvious quadratic answer, and the follow-up ladder tests whether you understood the argument or memorised the loop.

• 167 · Two Sum II — Input Array Is Sorted (Medium) — Practice selection. Probing whether you notice that "sorted" is a gift. Follow-up: for disk-backed data, opposite-end access needs backward/random access or suitable block buffering. This is not an algorithm for a forward-only stream; a hash method has a different retained-state cost.
• 11 · Container With Most Water (Medium) — Practice selection. Probing the hard discard proof. Follow-up: with nonnegative heights, any narrower pair retaining the shorter endpoint has height at most that endpoint and smaller width, so cannot improve on the current area. Equal heights allow either endpoint to be discarded.
• 15 · 3Sum (Medium) — Practice selection. Probing dedup discipline. Follow-up: "now do 4Sum" — the same recursion one level deeper, not a new idea.
• 125 · Valid Palindrome (Easy) — Practice selection. Probing the guarded skip loops. Follow-up: 680 · Valid Palindrome II, where you may delete one character — try both branches on the first mismatch.
• 42 · Trapping Rain Water (Hard) — Practice selection. Probing whether you can carry running max-left and max-right alongside the converging pointers. Follow-up: compare against the monotonic-stack solution that returns in L18.
• 977 · Squares of a Sorted Array (Easy) — Practice selection. Probing that you see the largest square is at one end and fill the output backwards.
• 16 · 3Sum Closest (Medium) — Practice selection. Probing that the skeleton also works for "nearest" objectives, not only exact hits.

The escalation to watch: nearly every one of these ends with a variant that keeps the walk and changes the objective. That is the tell that you were meant to learn the argument, not the four lines.

Complexity

For the exact-sum skeleton, at most max(n-1,0) pair comparisons give O(n) time and O(1) workspace under bounded integer operations. Early return can stop sooner; the palindrome version has a separate linear total-pointer-progress argument.

Sorting first adds O(n log n) worst-case comparisons. Python list.sort mutates the list but can use O(n) temporary workspace; sorted additionally returns a new list. Decorating values with original indices also requires O(n) storage. The later O(1)-workspace scan does not erase those costs.

For the shown 3Sum, a fixed-value loop and an O(n) suffix scan give O(n²) worst-case time plus sorting. CPython sorting makes auxiliary space O(n), even excluding output; the output can itself have Θ(n²) distinct value triples. A particular n bound does not certify judge runtime. With arbitrary-size integers, include arithmetic/comparison bit costs.

Self-check (answer follows each question).

Recall · L07

Q: Why is the loop condition lo < hi and not lo <= hi?

A: At lo == hi there is one element, not a pair. Allowing equality lets an element pair with itself, which is wrong whenever a value is exactly half the target.

Q: The sum is below target. Which pointer moves and what exactly does that eliminate?

A: lo moves up. Since a[hi] was the largest available partner, a[lo]'s best possible sum already fell short, so every pair containing a[lo] is eliminated — a whole row of the pair matrix.

Q: What precondition does the discard argument depend on, and what happens without it?

A: Sortedness. Without it, a[hi] is not the largest remaining value, so the elimination is unjustified — the algorithm returns wrong answers while still passing many random tests.

Q: In Valid Palindrome, why do the inner skip loops need their own lo < hi guard?

A: On input that is entirely non-alphanumeric, an unguarded skip walks the pointer past the end of the string and raises IndexError.

Q: In Container With Most Water, why always move the pointer at the shorter line?

A: For nonnegative heights, every narrower pair retaining the shorter endpoint has height at most that endpoint, so cannot exceed the area just evaluated. Discard that endpoint; if heights tie, either is safe. A new opposite endpoint could be even shorter, so the limiting height need not stay equal—it is bounded above.

Q: In 3Sum, why skip duplicates as you go rather than deduplicating the results at the end?

A: Post-filtering costs extra memory and an extra pass, and it hides the real invariant. Skipping inline — advance past equal values after recording a hit, and skip repeated values of the fixed element — keeps the output unique by construction at no extra cost.

Q: In the 3Sum inner loop, why must lo and hi each advance once unconditionally before the duplicate-skip while loops run?

A: In this version, the moves make lo-1 and hi+1 reference the matched endpoint values and keep those neighbor accesses valid. Removing both can raise IndexError, for example on [-2,0,2]. Other correct versions can explicitly save the matched values and skip relative to them; both unconditional moves are not universally required.

Q: Why is the early break on nums[i] > 0 in 3Sum correct, and what does it depend on?

A: It depends entirely on the sort. Once the smallest of the three chosen values is positive, all three are positive, so the sum cannot be zero — and every later i is at least as large. Without sorting the break is unsound.

Q: Stretch: Trapping Rain Water can be solved with converging pointers. What extra state do you carry, and which pointer moves?

A: One precise version maintains the highest bars already scanned from each end. While left <= right, first update each running maximum using its current endpoint. If max_left <= max_right, add max_left-height[left] and advance left; otherwise add max_right-height[right] and retreat right. The opposite scanned maximum certifies a boundary at least as high as the smaller maximum, so that side’s trapped depth is fixed. This assumes nonnegative heights and uses an accumulated total; handle empty input with zero iterations.

Stretch: true

Goal: Prove before you code

Hint: Write the sentence before writing the loop.

For each of the four problems in this session, write one sentence of the form: "when CONDITION, I move POINTER, which eliminates SET, because REASON." Four sentences. If you cannot write one for a problem, you do not yet have the pattern for it — and that is a far more useful finding than a passing submission.

Spaced queue

If an actual elapsed-day review date is due, revisit the failed Two Sum attempt and contrast it with sorted Two Sum II. Two session numbers do not imply two calendar days; schedule according to your own dates and load.

Optional queue defaults, not validated intervals: cold +60d, warm +21d, hint +7d, failed +2d then a later retest. Adjust after observing retention and workload.

• Sorted input plus pair-finding is the loudest cue in the entire series.

• The pattern is justified by a discard argument, not by being a leaner nested loop.

• a[hi] is the largest remaining value, so a[lo] + a[hi] is the best case for a[lo] — falling short kills a[lo] entirely.

• Loop condition is strict: lo == hi is one element, not a pair.

• Pointers never reverse, which is what bounds the work at n iterations.

• Return type, ordering, mutation and memory constraints inform the choice; none alone uniquely selects hashing or sorting.

Corrective source notes

• Binary Search - Algorithms for Competitive Programming — Binary search can find a transition in an arbitrary monotone Boolean predicate. Checked 2026-10-07.
• 9. Classes — Python 3.14.8 documentation — Multiple names can refer to the same object, so mutations and copied references must be distinguished. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.