Two pointers cheat sheet

Do two sorted prices add up to a target?

Put one pointer at the cheapest item and one at the dearest. If the pair is too small, only a dearer low item can help, so move the low pointer up; if too big, move the high pointer down. Each step rules out one item for good, so the sweep is O(n) time and O(1) space.

def has_pair(prices: list[int], target: int) -> bool:
    lo, hi = 0, len(prices) - 1
    while lo < hi:
        s = prices[lo] + prices[hi]
        if s == target:
            return True
        if s < target:
            lo += 1
        else:
            hi -= 1
    return False

Push the empty parking slots to the end

Keep a write pointer for where the next car goes. Scan with a read pointer; each car swaps into the write position and the write pointer advances. Cars keep their order because they are written in the order they are read. One pass, O(n) time, O(1) extra space.

def empties_to_end(slots: list[int]) -> list[int]:
    write = 0
    for read in range(len(slots)):
        if slots[read] != 0:
            slots[write], slots[read] = slots[read], slots[write]
            write += 1
    return slots

Does a banner read the same both ways?

Walk two pointers inward from both ends. Skip characters that are not letters or digits; otherwise compare the two characters case-insensitively and stop at the first mismatch. O(n) time and O(1) space, without building a cleaned copy of the string.

def reads_both_ways(banner: str) -> bool:
    lo, hi = 0, len(banner) - 1
    while lo < hi:
        if not banner[lo].isalnum():
            lo += 1
        elif not banner[hi].isalnum():
            hi -= 1
        elif banner[lo].lower() != banner[hi].lower():
            return False
        else:
            lo, hi = lo + 1, hi - 1
    return True

Merge two sorted shelves into one

Keep one pointer per shelf. Repeatedly take the smaller front item and advance that pointer; when one shelf runs out, append the rest of the other. Every item is taken once, so it is O(n + m) time and O(n + m) for the output.

def merge_shelves(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out: list[int] = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Remove repeated readings from a sorted log in place

Use a write pointer that marks the end of the kept part. Scan with a read pointer; whenever the reading differs from the last kept one, write it and advance. Sorted input guarantees repeats sit next to each other, so one pass is enough: O(n) time, O(1) extra space.

def dedupe(log: list[int]) -> list[int]:
    write = 0
    for read in range(len(log)):
        if write == 0 or log[read] != log[write - 1]:
            log[write] = log[read]
            write += 1
    del log[write:]
    return log

Count weight triples that stay under a limit

Sort the weights. Fix the smallest parcel i, then run two pointers lo = i + 1 and hi = end. If w[i] + w[lo] + w[hi] is under the limit, every parcel between lo and hi also works with i and lo, so add hi - lo and move lo up; otherwise move hi down. O(n²) time after an O(n log n) sort, versus O(n³) for all triples. The sorted copy takes O(n) space.

def count_triples(weights: list[int], limit: int) -> int:
    w = sorted(weights)
    total = 0
    for i in range(len(w) - 2):
        j, k = i + 1, len(w) - 1
        while j < k:
            if w[i] + w[j] + w[k] < limit:
                total += k - j  # every third pick in (j, k] fits
                j += 1
            else:
                k -= 1
    return total

Squared deviations in sorted order

The largest square comes from one of the two ends, because the most negative and the most positive values have the biggest magnitudes. Compare the ends, write the bigger square at the back of the output, and move that pointer inward. Filling from the back gives sorted output in one O(n) pass; the output takes O(n) space and the rest is O(1).

def sorted_squares(dev: list[int]) -> list[int]:
    out = [0] * len(dev)
    lo, hi = 0, len(dev) - 1
    for pos in range(len(dev) - 1, -1, -1):
        if abs(dev[lo]) > abs(dev[hi]):
            out[pos] = dev[lo] * dev[lo]
            lo += 1
        else:
            out[pos] = dev[hi] * dev[hi]
            hi -= 1
    return out

Is a short route hidden inside a long one?

Walk the long route once with a pointer into the short route. Whenever the current long stop equals the next needed short stop, advance the short pointer. If it reaches the end, the short route is hidden inside. O(n) time for a long route of length n, O(1) space.

def hidden_inside(short: str, long_route: str) -> bool:
    i = 0
    for stop in long_route:
        if i < len(short) and stop == short[i]:
            i += 1
    return i == len(short)

Sort a tray of three token colours in one pass

Keep three regions with pointers: low (end of 0s), mid (scanner) and high (start of 2s). A 0 at mid swaps to low and both advance; a 1 just advances mid; a 2 swaps to high and only high moves, because the item swapped in has not been checked yet. One pass, O(n) time, O(1) space.

def sort_tray(tray: list[int]) -> list[int]:
    low, mid, high = 0, 0, len(tray) - 1
    while mid <= high:
        if tray[mid] == 0:
            tray[low], tray[mid] = tray[mid], tray[low]
            low += 1
            mid += 1
        elif tray[mid] == 1:
            mid += 1
        else:
            tray[mid], tray[high] = tray[high], tray[mid]
            high -= 1
    return tray

When do two pointers work, and why?

Two pointers work when some order lets you discard one candidate per step: sorted values for pair sums, positions for in-place edits, or two sorted inputs for merging. The proof is always the same shape: show the item you drop cannot be part of any remaining answer. Then n steps cover O(n) candidates instead of O(n²) pairs.

Same-direction vs opposite-end pointers

Opposite-end pointers start apart and close in; each step drops one end, so they finish in at most n steps. Same-direction pointers both move forward: the fast one reads, the slow one writes or marks a window start, and each moves at most n times. Both are O(n) because no pointer ever moves backwards.

In place or a new list: what the interviewer means

In place means O(1) extra working memory: you rearrange the given list instead of building another one, and the caller sees the change. In Python, reassigning the parameter name only rebinds a local variable; mutate with index assignment, slice assignment or methods. The output list itself does not count as extra space when one is required.