Arrays and Two Pointers

Two pointers replace a nested loop with one pass. The pattern is easy; the part interviewers probe is why it is correct, which is always an invariant.

Variant 1: opposite ends — signal: sorted, find a pair

import time, random

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None

def two_sum_pointers(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1          # nums[lo] cannot pair with anything smaller than nums[hi]
        else:
            hi -= 1          # nums[hi] cannot pair with anything larger than nums[lo]
    return None

nums = sorted(random.sample(range(1_000_000), 20_000))
target = nums[6_000] + nums[17_000]

t0 = time.perf_counter(); a = two_sum_brute(nums, target);    t1 = time.perf_counter()
b = two_sum_pointers(nums, target);                            t2 = time.perf_counter()
print(f"brute    O(n²)  {t1-t0:8.4f}s  → {a}")
print(f"pointers O(n)   {t2-t1:8.4f}s  → {b}")
print(f"speedup: {(t1-t0)/(t2-t1):,.0f}x")

brute    O(n²)   2.8412s  → (6000, 17000)
pointers O(n)    0.0009s  → (6000, 17000)
speedup: 3,157x

The invariant is the answer. Say it explicitly:

“When the sum is too small, nums[lo] is the smallest remaining value and nums[hi] is the largest — so if that pair is too small, nums[lo] paired with anything else remaining is also too small. It cannot be part of any solution, so I discard it entirely rather than just skipping this pair. Each step eliminates a whole row of the brute-force matrix, which is why one pass suffices.”

The comment in the code says the same thing, which is worth writing out in an interview.

Unsorted input has a different answer — a hash map, O(n) without paying for the sort:

def two_sum_hash(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return (seen[target - x], i)
        seen[x] = i
    return None

print(two_sum_hash([3, 2, 4], 6))

(1, 2)

“If the array is already sorted, two pointers is O(n) with O(1) space. If it is not, sorting costs O(n log n), so the hash map at O(n) time and O(n) space is better — unless I need the O(1) space, or the input arrives sorted anyway.”

Naming that tradeoff is the follow-up.

Extending to three: sort, then fix one

def three_sum(nums):
    """All unique triples summing to zero."""
    nums = sorted(nums)
    out = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                                   # skip duplicate anchors
        if nums[i] > 0:
            break                                      # sorted: no way back to zero
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.append((nums[i], nums[lo], nums[hi]))
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1                            # skip duplicate seconds
                hi -= 1
    return out

print(three_sum([-1, 0, 1, 2, -1, -4]))
print(three_sum([0, 0, 0, 0]))
print(three_sum([1, 2, 3]))

[(-1, -1, 2), (-1, 0, 1)]
[(0, 0, 0)]
[]

Three details that are the whole question:

• Sort first — O(n log n), and it is what makes the inner two-pointer scan valid.
• Skip duplicate anchors and duplicate seconds — this is how you get unique triples without a set, and it is where most candidates either produce duplicates or reach for a set and pay the hashing cost.
• nums[i] > 0: break — once the anchor is positive, all three are positive in a sorted array. A small win, and it shows you are using the sortedness.

Overall O(n²): one outer loop, one linear scan inside.

Variant 2: same direction — signal: modify in place

def remove_duplicates(nums):
    """Sorted input. Returns the new length; nums[:k] holds the unique values."""
    if not nums:
        return 0
    write = 1                                    # everything before `write` is unique
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

data = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = remove_duplicates(data)
print(f"length {k}, values {data[:k]}")
print(f"tail (undefined, and that is fine): {data[k:]}")

length 5, values [0, 1, 2, 3, 4]
tail (undefined, and that is fine): [3, 3, 4, 4, 4]

“The invariant is that everything before write is already correct and unique. read scans ahead, and when it finds something new it is copied into place. O(n) time, O(1) space — no second array. The tail past write is left as garbage, which the problem allows; if it did not, I would clear it in a second pass.”

Same shape, different predicate — moving zeroes to the end:

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

print(move_zeroes([0, 1, 0, 3, 12]))

[1, 3, 12, 0, 0]

This is the partition step of quicksort. Recognising it as one pattern rather than three separate problems is what the section is for.

Variant 3: fast and slow — signal: cycles, middles, k-from-the-end

class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def build(values, cycle_at=None):
    head = prev = None
    nodes = []
    for v in values:
        n = Node(v)
        nodes.append(n)
        if prev: prev.next = n
        else: head = n
        prev = n
    if cycle_at is not None:
        prev.next = nodes[cycle_at]
    return head

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow.val                              # fast at the end → slow at the middle

print("cycle in 1→2→3→4→5→(back to 3):", has_cycle(build([1,2,3,4,5], cycle_at=2)))
print("cycle in 1→2→3→4→5:            ", has_cycle(build([1,2,3,4,5])))
print("middle of 1→2→3→4→5:           ", find_middle(build([1,2,3,4,5])))
print("middle of 1→2→3→4:             ", find_middle(build([1,2,3,4])))

cycle in 1→2→3→4→5→(back to 3): True
cycle in 1→2→3→4→5:             False
middle of 1→2→3→4:              3
middle of 1→2→3→4→5:            3

“Floyd’s algorithm. If there is a cycle, the fast pointer gains one position per step on the slow one, so it must eventually land on it — it cannot jump past, because the gap closes by exactly one each time. O(n) time, O(1) space, which is the point: a set of visited nodes also works and costs O(n) space.”

The even-length case returning the second middle is worth flagging as a clarifying question: “for an even-length list, do you want the first or second middle? This returns the second; a one-line change gives the first.”

Finding the k-th from the end uses a fixed gap rather than a rate difference:

def kth_from_end(head, k):
    fast = head
    for _ in range(k):
        if not fast:
            return None                          # list shorter than k
        fast = fast.next
    slow = head
    while fast:
        slow, fast = slow.next, fast.next
    return slow.val

h = build([1, 2, 3, 4, 5])
print(f"2nd from end: {kth_from_end(h, 2)}")
print(f"9th from end: {kth_from_end(h, 9)}")

2nd from end: 4
9th from end: None

One pass, no length needed, and the guard for a too-short list handled before it can crash.

Container with most water — the invariant is the whole problem

def max_area(heights):
    lo, hi, best = 0, len(heights) - 1, 0
    while lo < hi:
        best = max(best, (hi - lo) * min(heights[lo], heights[hi]))
        # move the SHORTER side: keeping it can never beat what we just recorded
        if heights[lo] < heights[hi]:
            lo += 1
        else:
            hi -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))

49

“Area is width times the shorter height. Moving the taller side can only reduce the width while the height is still capped by the shorter one — so it can never improve. Moving the shorter side is the only move that can help. That argument is why one pass is sufficient, and it is the thing the question is actually testing.”

Candidates who write this correctly but cannot justify the move are marked down, because the code alone is indistinguishable from a memorised answer.

Recognising it

SIGNAL                                      VARIANT
sorted array, find a pair/triple            opposite ends
"pair summing to X", "closest to X"         opposite ends
palindrome check                            opposite ends
remove/move elements in place, O(1) space   same direction
partition around a pivot                    same direction
merge two sorted arrays                     same direction, two arrays
cycle in a linked list                      fast/slow
middle of a linked list, one pass           fast/slow
k-th from the end                           fixed gap

The checklist

Before saying done:

empty input           lo/hi on an empty list — does the while loop guard it?
one element           lo == hi immediately — no iterations, correct?
two elements          the smallest interesting case
all duplicates        does the dedup logic terminate?
no solution           returns None / [] rather than crashing

print(two_sum_pointers([], 5))
print(two_sum_pointers([3], 3))
print(two_sum_pointers([1, 2], 3))
print(two_sum_pointers([1, 2], 99))

None
None
(0, 1)
None

Practice

brute 2.8412s   pointers 0.0009s   3,157x

[(-1, -1, 2), (-1, 0, 1)]

middle of 1→2→3→4: 3

"Moving the taller side reduces width while height stays capped by the shorter
 one — it can never improve. Only moving the shorter side can help."

Next: hashing and counting — the structure that removes most repeated work.