L07 · Two Pointers I — Opposite Ends

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

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.

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.