Array patterns · C++ templates

Two pointers, traced frame by frame

Four loop skeletons cover an enormous share of array and string problems. They look nearly identical written down, so the thing worth internalising isn't the syntax — it's what each pointer is allowed to do, and why the work stays linear. Every animation below runs the real algorithm on a real input; press play, or step through it one line at a time.

Pointers walking in from both ends

One index starts at the front, one at the back, and every iteration moves exactly one of them inward. The gap only ever shrinks, so the loop runs at most n times — that is the entire reason this beats the nested-loop version.

The part you actually have to design is the CONDITION: given what you can see at left and right, which side is safe to throw away forever?

The templateone array, converging indices

int fn(vector<int>& arr) {
    int left = 0;
    int right = int(arr.size()) - 1;
    int ans = 0;
    while (left < right) {
        // do some logic here with left and right
        if (CONDITION) {
            left++;
        } else {
            right--;
        }
    }
    return ans;
}

Traced: a pair summing to 12 in a sorted array

Because the array is sorted, a sum that is already too small can never be repaired by picking a smaller right-hand value — so the small side moves up. That single guarantee is what licenses discarding a candidate permanently, and it is what you have to be able to argue for in any problem of this shape.

1int hasPair(vector<int>& arr, int target) {

2 int left = 0;

3 int right = int(arr.size()) - 1;

4 int ans = 0;

6 while (left < right) {

7 int sum = arr[left] + arr[right];

8 if (sum == target) { ans = 1; break; }

9 if (sum < target) {

10 left++;

11 } else {

12 right--;

13 }

14 }

15 return ans;

16}

arr — sorted ascending

0123456

▲left

▲right

left0right6sum–target12ans0

left sits at the front, right at the back. Target is 12.

1 / 16

Practice — LeetCode

One pointer per array

Same idea, split across two inputs: i scans the first array, j the second, and each step advances whichever one is lagging. The main loop stops the moment either array runs out — which is why the template ends with two drain loops that flush whatever is left over.

Forgetting those tail loops is the classic bug here. Watch the last frames of the trace: the whole tail of a is appended by the loop on line 13, long after the main loop quit.

The templatetwo arrays, independent indices

int fn(vector<int>& arr1, vector<int>& arr2) {
    int i = 0, j = 0, ans = 0;
    while (i < arr1.size() && j < arr2.size()) {
        // do some logic here
        if (CONDITION) {
            i++;
        } else {
            j++;
        }
    }
    while (i < arr1.size()) {
        // do logic
        i++;
    }
    while (j < arr2.size()) {
        // do logic
        j++;
    }
    return ans;
}

Traced: merging two sorted arrays

Every frame appends exactly one element and advances exactly one pointer, so between them the two arrays are traversed once — O(n + m) time.

1vector<int> merge(vector<int>& a, vector<int>& b) {

2 int i = 0, j = 0;

3 vector<int> out;

5 while (i < a.size() && j < b.size()) {

6 if (a[i] <= b[j]) {

7 out.push_back(a[i]); i++;

8 } else {

9 out.push_back(b[j]); j++;

10 }

11 }

13 while (i < a.size()) { out.push_back(a[i]); i++; }

14 while (j < b.size()) { out.push_back(b[j]); j++; }

15 return out;

16}

▲i

▲j

out

i0j0out.size()0

Both indices start at 0 and out is empty. Neither array is ever re-read.

1 / 18

Practice — LeetCode

The read / write variant

Worth separating out, because it trips people up: here both pointers move in the same direction over the same array. read visits every element; write only advances when an element is worth keeping, so it trails behind and marks the boundary of the answer built in place.

Move Zeroes is the canonical one: keep every non-zero element by copying it to write, then fill arr[write..n-1] with zeros. Same O(n), same O(1) space, no extra array.

The templateone array, a fast reader and a slow writer

void fn(vector<int>& arr) {
    int write = 0;
    for (int read = 0; read < arr.size(); read++) {
        if (KEEP_CONDITION) {
            arr[write] = arr[read];
            write++;
        }
    }
    // arr[0 .. write-1] is the kept prefix
}

Practice — LeetCode

The sliding window

Here the pointers chase each other forward. right advances once per iteration and adds an element to the running state; left moves only when the window has gone invalid, and then only far enough to fix it.

The inner while is the part people misread as quadratic. It isn't: left never moves backwards, so across the entire run it advances at most n times in total, however it clusters. Two indices, one pass each — O(n).

The templateone array, both indices moving forward

int fn(vector<int>& arr) {
    int left = 0, ans = 0, curr = 0;
    for (int right = 0; right < arr.size(); right++) {
        // do logic here to add arr[right] to curr
        while (WINDOW_CONDITION_BROKEN) {
            // remove arr[left] from curr
            left++;
        }
        // update ans
    }
    return ans;
}

Traced: longest subarray with sum ≤ 8

curr is the window's state. Swap it for a frequency map, a distinct-character count or a zero counter and this same skeleton solves a dozen other problems without changing shape.

1int longestAtMost(vector<int>& arr, int k) {

2 int left = 0, ans = 0, curr = 0;

4 for (int right = 0; right < arr.size(); right++) {

5 curr += arr[right];

6 while (curr > k) {

7 curr -= arr[left];

8 left++;

9 }

10 ans = max(ans, right - left + 1);

11 }

12 return ans;

13}

arr

012345678

▲left

▲right

left0right–curr0k8ans0

left, curr and ans all start at 0. The budget k is 8.

1 / 35

Practice — LeetCode

Reading the problem statement

All four templates are a loop with two integers in it. What separates them is the question being asked, and these phrasings are reliable signals.

If the statement says…	Reach for	Because
“sorted array”, “a pair that sums to”, “palindrome”, “from both ends”	Converging pointers	One comparison eliminates an entire side, so the search space closes in from the outside.
“two sorted lists”, “merge”, “intersection of”, “common elements”	One pointer per array	Each input is consumed in order; advance whichever side is behind — and don’t forget the drain loops.
“in place”, “O(1) extra space”, “remove all …”, “move all …”	Read / write pointers	The answer is a prefix of the same array, and the writer marks where it ends.
“subarray”, “substring”, “contiguous”, “longest / shortest … such that”	Sliding window	Contiguity means a candidate is fully described by [left, right], so growing or shrinking it is cheap.
“at most k”, “no more than”, “contains no repeats”	Sliding window	That phrase is your WINDOW_CONDITION_BROKEN — negate it and you have written the while.
“exactly k”	Two windows	Compute atMost(k) − atMost(k−1); the exact-count version has no single valid window.

Say the invariant out loud

Before writing the loop, finish this sentence: “at every iteration, [left, right] is …”. If you can't, the condition isn't designed yet.

The off-by-one that always bites

A window's length is right − left + 1. Converging pointers want while (left < right) when the two must differ, and <= when the middle element still needs visiting.

Why a nested while is still linear

Count pointer moves, not loop nesting. Each index only ever increases and is bounded by n, so total work is bounded by 2n.