Two pointers on arrays

One array, two indexes

Most array loops use one index that walks from start to end. Many problems become simpler, and use less memory, when two indexes move through the array at once, each with its own job. The technique is called two pointers, although the "pointers" are usually plain indexes. It comes in three shapes, and each one is a single pass over the data with O(1) extra memory.

Shape 1: from both ends toward the middle

Put i at the start and j at the end, and move them toward each other until they meet. Each step deals with one pair of elements: the first and the last, then the second and the second-to-last, and so on.

The trace above uses this to test a palindrome. At each step it compares s[i] with s[j]. If a character doesn't count, such as a space or a comma, only that index moves on. If two counted characters differ, the answer is False immediately. If the indexes meet, every pair matched.

What makes this correct is an invariant, a statement that is true every time the loop reaches its top: every character to the left of i and to the right of j has already been matched with its partner. It is true at the start, when nothing is outside the range. Each step keeps it true. When i and j meet, nothing is left inside the range, so everything has been matched. Stating the invariant is the quickest way to convince yourself, or an interviewer, that a two-pointer loop is right, and it tells you exactly what to check at the boundaries.

Reversing an array is the same loop with a swap instead of a comparison, as in the previous module's trace. Reversing the words of a sentence builds on it: reverse the whole character array, then reverse each word back. "the sky is blue" becomes "eulb si yks eht", then "blue is sky the".

Shape 2: a read index and a write index

The second shape has both indexes moving in the same direction at different speeds. A read index visits every element. A write index marks where the next element worth keeping goes. Whenever the read index finds an element to keep, it copies it to the write index and advances both; otherwise only the read index moves.

def remove_value(a, val):
    write = 0
    for read in range(len(a)):
        if a[read] != val:
            a[write] = a[read]
            write += 1
    return write          # the new length

Everything before write is the finished result; everything from read onward hasn't been looked at; the region in between holds leftovers that will be overwritten or discarded. This is the batch-removal pattern from the previous lesson, and it solves a whole family of problems: removing a value, moving zeros to the end (keep the non-zeros, then fill the rest with zeros), and removing duplicates from a sorted array (keep an element when it differs from the last one written).

Shape 3: one index per array

The third shape walks two different arrays, one index each. The classic case is merging two sorted arrays: compare the elements at the two indexes, take the smaller, advance that index, repeat. Each comparison places one element, so merging arrays of sizes m and n takes m + n steps. This is the merge step of merge sort, which you will meet in the sorting module.

A common variant asks for the merge to happen in place: nums1 has extra empty slots at its end, exactly enough to hold nums2. Merging from the front would overwrite elements of nums1 before they had been compared. The fix is to merge from the back: put one index at the last real element of each array and a write index at the last slot, and place the largest remaining element each time. The free slots are at the back, so the write index always stays at or ahead of the unread part of nums1, and nothing is overwritten too early. The interview question for this lesson asks you to explain exactly that.

Why it is fast

All three shapes share the same cost argument. Each step moves at least one index forward (or inward), and no index ever moves backward, so the total number of steps is at most the combined length of the ranges. That is O(n) time. The only extra memory is the indexes themselves: O(1).

Compare the alternatives. A palindrome test that first builds a cleaned, lowercased copy and then compares it with its reverse also takes O(n) time, but allocates two new strings. A filter that calls remove for each unwanted element takes O(n²). Two pointers keeps the linear time and drops the extra memory.

Where this goes next

These three shapes reappear throughout the track. The fast and slow pointers of the linked lists module are shape 2 applied to a list. The patterns module in the Core level uses shape 1 on sorted arrays to find pairs with a given sum in linear time, and extends shape 2 into the sliding window, where the two indexes mark the edges of a range that grows and shrinks. In every case, the way to get the loop right is the same: say what is true of the elements outside the indexes, and check that each step keeps it true.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Two pointers on arrays from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

i, j = 0, len(s) - 1
while i < j:
    if not s[i].isalnum(): i += 1; continue
    if not s[j].isalnum(): j -= 1; continue
    if s[i].lower() != s[j].lower(): return False
    i += 1; j -= 1
return True

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.