Two pointers

The two-pointer family covers converging walks on sorted data, trailing read-and-write compaction, and fast-and-slow cycle detection. What unites them is not the shape of the code but an elimination argument: every pointer move must permanently rule out a set of candidate answers, and the linear bound follows from the pointers never moving backwards. This guide develops that invariant, works through the pair, partition, cycle, merge, and water problems it solves, and is explicit about what the pattern actually buys — constant space rather than speed — and about the preprocessing costs that a complexity claim has to include.

the two-pointer invariant

A two-pointer solution is correct only because of an invariant that says what the untouched region can no longer contain, and stating that invariant is the whole technique.

Each move must eliminate a set of candidate answers permanently, so the loop can advance without ever revisiting them, which is what turns a quadratic search into a linear scan.

Each move discards a whole row or column of the implicit pair matrix.

# Invariant: every pair (i, j) with i < lo or j > hi has already been ruled out.
lo, hi = 0, len(a) - 1
while lo < hi:
    s = a[lo] + a[hi]
    if s == target: return lo, hi
    if s < target: lo += 1     # discards every pair (lo, k) for k <= hi
    else: hi -= 1              # discards every pair (k, hi) for k >= lo

Interview trap. Writing the loop first and adjusting the pointer moves until the sample passes produces code that is correct on the example and wrong on an input that reaches the eliminated region.

Engineering practice. Write the invariant as a sentence before the loop, and justify each pointer move by naming the candidates it discards.

opposite-end pointers on a sorted array

On a sorted array, two pointers converging from the ends decide a pair-sum question in one linear pass.

If the current pair sums below the target, only a larger left value can help, so the left pointer advances; if it sums above, only a smaller right value can help, so the right pointer retreats — each move eliminates an entire row or column of the implicit pair matrix.

On [1, 3, 4, 6] with target 7 the walk takes three steps, not six comparisons.

a, target = [1, 3, 4, 6], 7
# lo=0 hi=3 -> 1+6=7  found at (0, 3)
# On an unsorted [1, 6, 3, 4] the same walk returns nothing and misses 3+4:
# 1+4=5 advances lo, then 6+4 and 6+3 both retreat hi until the pointers meet.
# The permutation [6, 1, 4, 3] happens to find 6+1, which is why a lucky trace is not a proof.

Interview trap. Applying the same walk to an unsorted array is the most common failure: the elimination argument depends entirely on the ordering.

Engineering practice. Confirm or establish the ordering first, and if sorting is needed, budget the O(n log n) and check whether the original indices must be preserved.

same-direction pointers

Two pointers moving in the same direction express a read position and a write or boundary position, and neither ever moves backwards.

The read pointer visits each element once while the trailing pointer advances only when the invariant permits, so the total work is linear even though the pointers move at different rates.

The trailing pointer stalls; the reading pointer never does.

write = 0
for read in range(len(a)):        # advances every iteration
    if keep(a[read]):
        a[write] = a[read]
        write += 1                # advances only when the invariant allows

Interview trap. Assuming both pointers advance once per iteration turns the pattern back into a fixed-offset comparison and loses the cases where the trailing pointer must stall.

Engineering practice. Drive the loop from the read pointer, advance the trailing pointer only inside its condition, and assert the invariant about the prefix before the trailing pointer.

in-place deduplication

Removing duplicates from a sorted array is a same-direction two-pointer compaction in O(1) extra space.

The write pointer marks the end of the deduplicated prefix; each new element is written only when it differs from the last kept element, and the function returns the prefix length rather than resizing.

Return the length, not the array: elements past it are stale.

def dedupe(a):                    # a is sorted
    if not a: return 0
    write = 1
    for read in range(1, len(a)):
        if a[read] != a[write - 1]:
            a[write] = a[read]; write += 1
    return write

a = [1, 1, 2, 3, 3]
dedupe(a)     # 3; a == [1, 2, 3, 3, 3] - a[3:] is unspecified

Interview trap. Returning the array itself rather than the logical length leaves stale elements past the boundary that callers will read.

Engineering practice. Return the new length and document that elements beyond it are unspecified, or truncate explicitly if the language makes that cheap.

partitioning around a predicate

Two pointers can partition an array into elements satisfying a predicate and those that do not, in one pass and in place.

A boundary pointer marks the end of the satisfying prefix; when the scanning pointer finds a satisfying element it is swapped to the boundary and the boundary advances.

The swap destroys relative order inside each part.

a = [1, 2, 3, 4, 5, 6]
boundary = 0
for i in range(len(a)):
    if a[i] % 2 == 0:
        a[boundary], a[i] = a[i], a[boundary]; boundary += 1
print(a)      # [2, 4, 6, 3, 1, 5] - evens first, but 3 now precedes 1

Interview trap. Assuming the partition is stable is wrong — the swap moves an arbitrary element into the vacated slot, so relative order within each part is destroyed.

Engineering practice. Use the in-place partition when order is irrelevant, and allocate a second array when stability is part of the requirement.

three-pointer partitioning

Sorting an array with three distinct values takes one pass with three pointers, the Dutch-national-flag arrangement.

Low, mid, and high pointers maintain three regions and an unexamined middle; the mid pointer advances only when it swaps forwards, because a swap from the high end brings in an element that has not yet been classified.

Advancing mid after a high swap skips the element just brought in.

def sort_three(a):
    lo, mid, hi = 0, 0, len(a) - 1
    while mid <= hi:
        if a[mid] == 0:
            a[lo], a[mid] = a[mid], a[lo]; lo += 1; mid += 1
        elif a[mid] == 2:
            a[mid], a[hi] = a[hi], a[mid]; hi -= 1     # mid does NOT advance
        else:
            mid += 1

Trace [2, 0, 1]: the first swap brings 1 to index 0, and advancing mid would leave it unexamined.

Interview trap. Advancing mid after a swap with the high pointer skips the element just brought in and leaves it misplaced.

Engineering practice. Write the three cases explicitly and trace an input where the high swap brings back the smallest value, which is the case that exposes the bug.

removing duplicates in pair search

When a pair or triple search must report distinct value combinations rather than distinct index combinations, the skip logic is part of the algorithm rather than a post-processing step.

After a successful match, both pointers advance past every element equal to the one just used, so the same value combination cannot be produced twice.

Skip at the point of advancing, or an all-equal input produces O(n^2) duplicate results.

while lo < hi:
    s = a[lo] + a[hi]
    if s == target:
        out.append((a[lo], a[hi]))
        lo += 1; hi -= 1
        while lo < hi and a[lo] == a[lo - 1]: lo += 1     # skip equal values
        while lo < hi and a[hi] == a[hi + 1]: hi -= 1

On [2] * 10_000 with target 4 this returns one pair; deduplicating afterwards would build 5,000 first.

Interview trap. Deduplicating the result list afterwards is both slower and hides a quadratic blow-up when the input is largely one repeated value.

Engineering practice. Skip duplicates at the point of advancing, and test an input of identical values, which is where the difference between the two approaches becomes visible.

reducing a triple to a pair

A three-element search on a sorted array is a loop over the first element wrapping the two-pointer pair search, giving O(n squared).

Fixing one element reduces the problem to finding a pair with the complementary target in the remaining suffix, which the converging pointers answer in linear time.

Fixing one element makes the rest a pair search: O(n^2), not O(n^3).

a.sort()
for i in range(len(a) - 2):                    # n iterations
    lo, hi = i + 1, len(a) - 1
    while lo < hi:                             # n more, total O(n^2)
        s = a[i] + a[lo] + a[hi]
        ...

At n = 2,000 that is 4 million steps instead of 8 billion.

Interview trap. Claiming the hashing approach is strictly better ignores that it needs O(n) memory and additional care to avoid reusing an index.

Engineering practice. Choose the sorted two-pointer version when memory matters or output must be ordered, and the hashing version when the input cannot be reordered.

the container-of-water argument

Converging pointers solve the maximum-area problem because moving the taller side can never improve the result.

Area is limited by the shorter side and the width shrinks with every move, so keeping the shorter side fixed while shrinking the width can only reduce the area — which makes discarding the shorter side safe.

Moving the taller side can only shrink the area, so discarding the shorter one is safe.

h = [1, 8, 6, 2, 5, 4, 8, 3, 7]
lo, hi, best = 0, len(h) - 1, 0
while lo < hi:
    best = max(best, (hi - lo) * min(h[lo], h[hi]))
    if h[lo] < h[hi]: lo += 1      # always move the limiting side
    else: hi -= 1
best     # 49

Interview trap. Moving whichever pointer looks locally promising is a greedy guess without the elimination proof, and it fails on inputs where the taller side hides a better partner.

Engineering practice. Always move the limiting side, and be able to state the exchange argument that shows nothing better was discarded.

fast and slow pointers

Two pointers advancing at different rates detect a cycle in a sequence in constant space.

If a cycle exists, the faster pointer eventually laps the slower one and they meet inside the cycle; if it does not, the faster pointer reaches the end first.

The meeting point is inside the cycle, not at its entry.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast: break        # met somewhere inside the cycle

On 1 -> 2 -> 3 -> 4 -> back to 2, the pointers meet at 4, while the entry is 2.

Interview trap. Concluding that the meeting point is the cycle entry is wrong — it is a point inside the cycle, and finding the entry needs a second phase.

Engineering practice. Use the meeting point only as evidence a cycle exists, then run the second walk from the head to locate the entry.

locating the cycle entry

After the pointers meet, restarting one at the head and advancing both one step at a time makes them meet exactly at the cycle entry.

The distance from the head to the entry equals the distance from the meeting point to the entry modulo the cycle length, which is what makes the second phase land precisely.

Phase two moves both pointers one step, which is what makes the modular argument land.

head_ptr = head
while head_ptr is not slow:       # slow is the meeting point
    head_ptr = head_ptr.next
    slow = slow.next              # one step each - two would overshoot
entry = head_ptr

Interview trap. Advancing the second-phase pointers at different rates breaks the modular argument and produces an answer inside the cycle instead of at its entry.

Engineering practice. Keep the second phase strictly one step each, and test a cycle whose entry is the head, which is the degenerate case that off-by-one errors break.

finding the middle in one pass

A fast pointer moving twice as quickly leaves the slow pointer at the middle when it reaches the end, with no length precomputation.

The slow pointer covers half the distance in the same number of steps, so its position when the walk ends is the midpoint by construction.

The loop condition decides which middle you get on an even-length list.

# 1 -> 2 -> 3 -> 4
while fast and fast.next:  slow = slow.next; fast = fast.next.next   # slow = 3 (second middle)
while fast.next and fast.next.next: slow = slow.next; fast = fast.next.next  # slow = 2 (first)

Interview trap. The two possible loop conditions differ on even-length inputs — one lands on the first middle element and the other on the second — and the callers usually care which.

Engineering practice. Decide which middle the caller needs, encode it in the loop condition, and cover both parities in tests.

palindrome checks

Comparing from both ends inwards decides a palindrome in linear time and constant space.

Each step compares one pair and eliminates it; the loop ends when the pointers cross, which happens after roughly half the length.

Skipping in the walk keeps the space constant; preprocessing does not.

def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        while lo < hi and not s[lo].isalnum(): lo += 1
        while lo < hi and not s[hi].isalnum(): hi -= 1
        if s[lo].lower() != s[hi].lower(): return False
        lo += 1; hi -= 1
    return True

is_palindrome("A man, a plan, a canal: Panama")   # True, O(1) extra space

Interview trap. Filtering or normalising the input into a new string first is correct but abandons the constant-space property that the question was usually asking about.

Engineering practice. Skip ignorable characters in the walk itself rather than preprocessing, and be explicit about what the comparison considers equal.

merging two sorted sequences

One pointer per sequence merges two sorted inputs in time linear in their combined length.

Each step emits the smaller head and advances only that pointer, so every element is examined exactly once and ordering is preserved.

Forgetting the drain silently truncates the result.

i = j = 0; out = []
while i < len(a) and j < len(b):
    if a[i] <= b[j]: out.append(a[i]); i += 1     # <= keeps the merge stable
    else: out.append(b[j]); j += 1
out += a[i:]; out += b[j:]                        # the drain - not optional

Interview trap. Forgetting to drain the sequence that still has elements after the other is exhausted silently truncates the result.

Engineering practice. Write the drain steps as part of the merge rather than as an afterthought, and choose the comparison direction deliberately so the merge stays stable.

merging in place from the back

Merging a shorter sorted array into a larger one that already has room is done from the back, not the front.

Writing from the highest index backwards means the write pointer is always ahead of both read pointers, so no unread element is ever overwritten.

Writing forwards overwrites elements that have not been read yet.

def merge(a, m, b, n):        # a has n spare slots at the end
    i, j, w = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and a[i] > b[j]: a[w] = a[i]; i -= 1
        else: a[w] = b[j]; j -= 1
        w -= 1

a = [4, 5, 6, 0, 0, 0]; merge(a, 3, [1, 2, 3], 3)   # [1, 2, 3, 4, 5, 6]

The forward version corrupts exactly when b's elements are all smaller.

Interview trap. Merging forwards into the same array overwrites elements that have not yet been read, and the corruption depends on the data so it often survives the first test.

Engineering practice. Start the write pointer at the last usable slot, and check the case where the shorter array's elements are all smaller, which is where the forward version fails first.

the trapping-water two-pointer argument

Water above each position is bounded by the smaller of the maximum heights to its left and right, and converging pointers compute this without storing either array.

The pointer on the side with the smaller running maximum can be resolved immediately, because the other side is already known to be at least as tall.

Running maxima, not current heights, are what make the side resolvable.

h = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
lo, hi, lmax, rmax, water = 0, len(h) - 1, 0, 0, 0
while lo < hi:
    if h[lo] < h[hi]:
        lmax = max(lmax, h[lo]); water += lmax - h[lo]; lo += 1
    else:
        rmax = max(rmax, h[hi]); water += rmax - h[hi]; hi -= 1
water    # 6

Interview trap. Using the current heights rather than the running maxima gives a plausible-looking solution that is wrong whenever a taller wall lies further out.

Engineering practice. Track the running maxima explicitly, and validate against the straightforward prefix-and-suffix-maximum version on random inputs.

two pointers over two different sequences

The technique generalises beyond one array: one pointer per sequence solves intersection, difference, and interval-alignment problems in linear time when both are sorted.

Comparing heads decides which pointer advances, and equality is the only case that emits output, so each element of each input is visited once.

Advance only the smaller head; advancing both skips matches.

i = j = 0
while i < len(a) and j < len(b):
    if a[i] == b[j]: out.append(a[i]); i += 1; j += 1
    elif a[i] < b[j]: i += 1        # only the smaller side moves
    else: j += 1

# a = [1, 2, 4], b = [2, 3, 4] -> [2, 4]

Interview trap. Advancing both pointers on a mismatch skips elements and produces a result that is missing entries.

Engineering practice. Advance only the pointer with the smaller head on a mismatch, and state which of the three branches emits output.

two pointers versus binary search

Two pointers give a linear scan over a sorted array; binary search gives a logarithmic lookup for a single query, and the choice follows from how many queries there are.

Answering n queries by binary search costs O(n log n) total, while a coordinated linear walk answers all of them in O(n) — but only when the queries themselves arrive in sorted order.

n binary searches cost O(n log n); one coordinated walk costs O(n).

import bisect
# 100,000 sorted queries against a 1,000,000-element sorted array:
[bisect.bisect_left(data, q) for q in queries]   # ~100,000 x 20 = 2,000,000 probes
# The merge walk touches each of the 1,100,000 elements once instead.

Interview trap. Reaching for binary search inside a loop over a sorted array is a common way to add a logarithmic factor that the walk would have avoided.

Engineering practice. When both the data and the queries are ordered, walk them together; keep binary search for isolated or unordered queries.

the cost of sorting first

Sorting to enable two pointers changes the complexity class, so it must be justified rather than assumed free.

The solution becomes O(n log n) dominated by the sort, which is still better than a quadratic scan but worse than a hash-based linear pass when one exists.

The walk is linear; the solution is not, because the sort dominates.

a.sort()                 # O(n log n) - this is the complexity of the solution
lo, hi = 0, len(a) - 1   # O(n)

At n = 1,000,000 the sort is roughly 20 million comparisons and the walk is 1 million steps.

Interview trap. Reporting the solution as linear because the pointer walk is linear ignores the sort that made the walk possible.

Engineering practice. Quote the total complexity including preprocessing, and say what the sort bought — ordering in the output, constant space, or the elimination argument itself.

index stability under sorting

Sorting destroys the original positions, so a problem that must report indices needs them carried along or recovered.

Pairing each value with its original index before sorting preserves the mapping at the cost of the extra array; the alternative is to solve the problem without reordering at all.

Sorting in place returns positions into the sorted array, which mean nothing to the caller.

a = [3, 1, 2]
pairs = sorted((v, i) for i, v in enumerate(a))   # [(1, 1), (2, 2), (3, 0)]
# pairs[0][1] == 1 is the original index of the smallest value.
# a.sort() alone would have destroyed that mapping.

Interview trap. Sorting in place and then reporting the pointer positions returns indices into the sorted array, which are meaningless to the caller.

Engineering practice. Decide up front whether the answer is values or positions, and if it is positions, prefer the hash-based approach that never reorders.

loop termination and crossing

Whether the loop ends when the pointers meet or after they cross is a decision about whether a single element is a valid answer.

A strict inequality stops with the pointers adjacent or equal and never examines the one-element case; a non-strict one examines it.

< never examines a one-element range; <= does.

while lo < hi:   ...   # stops with lo == hi: the single-element window is never seen
while lo <= hi:  ...   # examines it - required when a length-1 answer is admissible

Interview trap. Copying the loop condition from a similar problem is the standard source of off-by-one defects in this family.

Engineering practice. Derive the condition from whether a length-one or length-zero window is admissible, and test both empty and single-element inputs.

constant space as the real benefit

The main advantage of two pointers over a hash-based solution is usually memory, not speed, since both are linear in time.

The walk carries a fixed number of indices regardless of input size, which lets it run over data far larger than a hash index would allow.

Both are linear in time; only one is constant in memory.

import sys
a = list(range(1_000_000))
sys.getsizeof(set(a))    # 33,554,656 bytes for the hash approach
# The two-pointer walk carries two integers: 56 bytes.

Interview trap. Presenting two pointers as faster than hashing invites a challenge that the candidate cannot support, since both do a linear number of operations.

Engineering practice. Make the claim about space, and name the constraint — memory limit, streaming input, embedded target — that makes it decisive.

immutability of the input

Whether the input may be modified is part of the problem statement and decides whether the in-place variants are admissible at all.

Sorting, partitioning, and in-place compaction all mutate the caller's data, which is a visible side effect when the array is shared.

Sorting mutates the caller's list, and the test that passes a fresh literal never notices.

def solve(a):
    a.sort()          # visible side effect on the caller's list
    ...

data = [3, 1, 2]
solve(data)
data              # [1, 2, 3] - the caller's order is gone

Use a = sorted(a) when mutation is not part of the contract.

Interview trap. Assuming an argument may be reordered is a defect that unit tests rarely catch, because they usually pass a freshly built array.

Engineering practice. Ask whether mutation is permitted, copy when it is not, and document mutation in the signature or the docstring when it is.

proving linearity

The linear bound holds because each pointer moves monotonically and never resets, giving at most 2n total moves.

The argument is a potential function: the sum of the distances the pointers still have to travel decreases with every iteration and never increases.

At most 2n pointer moves, because neither pointer is ever assigned backwards.

# lo only ever increases, hi only ever decreases, and they meet once:
# total moves <= (n - 1) + (n - 1) < 2n, whatever the data.
# A loop body containing `lo = i + 1` for an inner index breaks that argument -
# and with it the linear bound.

Interview trap. A nested loop that resets an inner pointer on each outer step looks like a two-pointer solution but is quadratic, and the monotonicity check is what catches it.

Engineering practice. Verify that no pointer is ever assigned backwards inside the loop, and if one is, account for the true cost rather than assuming the pattern's bound.

recognising the pattern

Two pointers apply when the input has an ordering — of values, of positions, or of time — that lets one move eliminate a whole class of candidates.

Without such an ordering there is no elimination argument, and the technique degenerates into a nested loop with extra variables.

No ordering means no elimination, and the pattern degenerates into a nested loop.

Input property	Two pointers	Why
Sorted values	yes	a move rules out a whole set of pairs
Positional order only	yes, same direction	the prefix is finished
Unsorted, pair sum	no - use a hash map	nothing licenses discarding a side
Subsequence, not subarray	no	elements need not be adjacent

Interview trap. Reaching for the pattern because the input is an array is the most reliable way to produce a subtly wrong solution.

Engineering practice. Ask what ordering the problem provides and what each move rules out; if neither question has an answer, choose a different technique.