L07 · Two Pointers I — Opposite Ends

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

Watch first

Why this session exists

Sorted input plus pair-finding equals two pointers. That cue alone solves dozens.

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 turns an O(n^2) search over pairs into an O(n) walk, and the reason it is allowed to is a short, provable argument rather than a trick.

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.

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?

The skeleton is four lines and you will get it. The argument is the part that decays, and it is the part that lets you adapt the skeleton to a variant you have not seen.

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 pair not yet examined 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):
    """a MUST be sorted. Returns a pair summing to target, 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 iteration kills exactly one element. n elements, so at
# most n iterations. That is the O(n).

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. Getting this wrong is the single most common reason 3Sum fails.

The cue

Five tells that this is the pattern:

1. The word "sorted" in the input description. It is never mentioned decoratively. If the input is sorted, the setter is telling you that order carries information you are meant to use.
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. "Find a pair such that ..." with a comparison against a target. Sum, difference, product against a threshold — anything where moving an endpoint moves the objective monotonically.
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.

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 tempting one-liner first, because you should know it and then reject it:

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

That is correct and it is what I would write in production. It builds a filtered copy and then a reversed copy, so it is O(n) time and O(n) space. The interview version removes the space:

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 harmless but pointless; walking past it is wrong. 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 interviewers do ask.

Cost: O(n) time, O(1) space. Compare honestly against the one-liner: same time class, strictly better space, more lines and more places to be wrong. On a real codebase I would ship the one-liner.

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 to yourself why moving the taller one can never help before you write anything; that proof is the entire problem.
• 3Sum — sort, fix one index, then run the converging skeleton on the remainder. The difficulty is not the algorithm, it is deduplication. 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.
• Moving both pointers when the sum matches, in a counting problem. If the array contains a run of equal values, the correct handling depends on whether a[lo] == a[hi]; handle that case separately or you will double count.

Worked variant — 3Sum, with the deduplication annotated

Two Sum II is the skeleton. 3Sum is where people actually lose the interview, and never on the algorithm — always on producing duplicate triplets. Here is the full thing with every dedup decision called out.

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. Moving only one produces the same triplet
                # again on the next iteration.
                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

The two dedup sites are structurally different and it is worth being able to say so. DEDUP 1 is a pre-check on the fixed element and looks backward (nums[i - 1]). DEDUP 2 is a post-advance after recording a hit and also looks backward, but only after the pointer has already moved once — that unconditional lo += 1; hi -= 1 before the skip loops is the line people forget, and forgetting it turns the inner while into an infinite loop on input like [0, 0, 0, 0].

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 — check the precondition before anything else. No ordering, no discard argument, no pattern. If the problem did not hand you sortedness, either establish it yourself or reach for a hash map.
• Squeeze — the hands only ever move inward. lo never decreases, hi never increases. That one-directional property is the entire complexity proof.
• Kill one — every iteration must permanently eliminate exactly one element, and you must be able to name which and why. If a proposed pointer move does not kill anything, it is a guess and the loop may not terminate correctly.

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 interviewers 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) — Amazon, Meta. Probing whether you notice that "sorted" is a gift. Follow-up: "the array has a million entries and lives on disk" — the two-pointer walk is sequential and streams; a hash map does not.
• 11 · Container With Most Water (Medium) — Amazon, Google, Bloomberg. Probing the hard discard proof. Follow-up: "convince me moving the taller line can never help" — width strictly decreases and the height is still capped by the shorter line.
• 15 · 3Sum (Medium) — Meta, Amazon, Adobe, Microsoft. Probing dedup discipline. Follow-up: "now do 4Sum" — the same recursion one level deeper, not a new idea.
• 125 · Valid Palindrome (Easy) — Meta, Amazon. 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) — Amazon, Google, Meta. 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) — Meta, Amazon. Probing that you see the largest square is at one end and fill the output backwards.
• 16 · 3Sum Closest (Medium) — Amazon, Bloomberg. 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 converging skeleton: time O(n) — each iteration advances exactly one pointer toward the other and neither ever reverses, so the total number of iterations is bounded by the initial gap, n - 1. Space O(1) — two indices.

When you must sort first, the total becomes O(n log n) dominated by the sort, with the walk vanishing under the max rule. Space is O(1) if sorting in place, O(n) if you use sorted() or must preserve indices.

For 3Sum specifically: an outer loop over the fixed element times an inner O(n) walk gives O(n^2) time, plus the O(n log n) sort which disappears. Space is O(1) beyond the output. Note that O(n^2) is not a failure here — with n up to about 3000, L01's table says quadratic is exactly the intended budget.

Spaced queue

Due today: anything from L05 marked failed comes back at plus two days, so Two Sum may return — and note the deliberate contrast, since today's Two Sum II is the same problem with sortedness granted. Solve them back to back and articulate why the technique differs.

Status ladder: cold +60d, warm +21d, hint +7d, failed +2d then +7d.