Arrays and Two Pointers

The array is the workhorse of coding interviews, and the two-pointer pattern is the single most reused idea for making array code fast. The trick is embarrassingly simple: instead of nesting one loop inside another (which costs $O(n^2)$), you keep two indices moving through the array under a rule that lets each one advance at most n times. The whole scan then costs $O(n)$, one pass, and usually $O(1)$ extra memory.

There are two flavours worth knowing. In the opposite-ends version, one pointer starts at the left, the other at the right, and they walk toward each other, this is the pattern for sorted-array problems, palindromes, and "container with most water". In the fast/slow (same-direction) version, both start at the left and one moves ahead of the other, this is the pattern for removing elements in place, detecting a cycle, or growing a window (the basis of the The Sliding Window Technique).

The opposite-ends idea

Suppose the array is sorted and you want two elements that add up to a target T. Point L at the smallest value and R at the largest, then look at their sum:

• if a[L] + a[R] is too small, the only way to grow it is to move L right to a bigger number;
• if it is too large, move R left to a smaller number;
• if it equals T, you are done.

Each move eliminates one number for good, so the pointers meet after at most n steps. That sortedness is what lets you make a confident decision at every step, without it, moving a pointer would not reliably shrink or grow the sum.

Worked example: two-sum on a sorted array

Take a = [2, 7, 11, 15, 20, 26, 31, 40] and target T = 42.

• L = 0 (value 2), R = 7 (value 40). Sum $= 42 = T$. Done on the first look, indices (0, 7).

Now try T = 33:

• 2 + 40 = 42 > 33, too big, move R left to 31.
• 2 + 31 = 33 = T. Done, indices (0, 6).

And T = 100:

• 2 + 40 = 42 < 100, move L right to 7.
• 7 + 40 = 47 < 100, move L to 11, then 15, 20, 26, 31 — every sum with 40 stays under 100 until the pointers cross. No pair exists, so return "not found".

In code:

def two_sum_sorted(a, T):     # O(n) time, O(1) space
    L, R = 0, len(a) - 1
    while L < R:
        s = a[L] + a[R]
        if s == T:
            return (L, R)
        elif s < T:
            L += 1            # need a bigger sum
        else:
            R -= 1            # need a smaller sum
    return None

The brute force compares every pair, $O(n^2)$. Two pointers do it in one pass. Even if the array arrives unsorted, sorting first ($O(n \log n)$) and then scanning still beats $O(n^2)$, though a hash map solves unsorted two-sum in plain $O(n)$.

The fast/slow variant

Both pointers start at the left; the slow one marks where the next "kept" element goes while the fast one scans ahead. This does in-place work with no extra array, for example, removing duplicates from a sorted array or moving all zeros to the end. The same shape, with one pointer jumping two steps and the other one, is Floyd's cycle-detection ("tortoise and hare") for linked lists.

Where it goes wrong

• Forgetting the sort precondition. Opposite-ends logic is only valid on sorted (or otherwise monotone) data. On unsorted input it silently returns wrong answers.
• Off-by-one and the crossing test. Use while L < R for pairs (never L <= R, which would pair an element with itself), and be deliberate about when you advance which pointer.
• Duplicates. For three-sum and similar, you must skip over equal neighbours after a match or you will emit the same triplet many times.

In quant-dev screens this pattern is everywhere: two-sum, three-sum, container-with-most-water, valid-palindrome, merge two sorted arrays, and partition problems. It also underpins the The Sliding Window Technique and pairs naturally with Prefix Sums and Binary Search Patterns when you need range or ordered structure.