Lesson 31

Spotting a Two-Pointer Subproblem: Rotating an Array Left

Spotting a Two-Pointer Subproblem

Some problems do not look like two-pointer problems at first. But if you break them into smaller pieces, one or more of those pieces *is* a two-pointer problem. Solving those pieces then solves the whole thing. These are usually the harder problems, because seeing the hidden pieces takes a little practice.

Two simple questions help you check if a problem hides a two-pointer piece inside it:

Q1. Can the problem (or its solution) be broken into smaller subproblems?
Q2. Can any of those subproblems be solved using the two-pointer technique?

Let's learn this through one clear example.

The problem: rotate an array `k` times to the left

We are given an array arr of integers and a number k. We must rotate the array k times to the left.

"Rotating left once" means every item moves one step to the left, and the item that falls off the front goes to the back. Do that k times.

With n = 8 and k = 4:

arr (before):  1 2 3 4 5 6 7 8
arr (after):   5 6 7 8 1 2 3 4

Notice what happened: the first 4 items (1 2 3 4) moved to the end, and the last 4 items (5 6 7 8) moved to the front. Each item simply landed k positions earlier than where it started.

Brute-force solution (using a temporary array)

The most obvious idea: make a second array, and copy each item into its new, shifted spot.

For an item at index i, its new index after rotating left by k is (i + k) % n. The % n (remainder) is what wraps items around to the back when they would fall off the front.

The steps are:

Create a temporary array temp of the same size.
For each i, copy arr[i] into temp at the shifted index.
Copy everything from temp back into arr.

void kRotate(vector<int> &arr, int k) {
    int n = arr.size();
    // Normalize k to avoid unnecessary rotations
    k = k % n;
    // Create a temporary array of same size
    vector<int> temp(n);
    // Copy items in temp array starting from index k
    for (int i = 0; i < n; i++) {
        // Rotate if we go out of bounds
        temp[i] = arr[(i + k) % n];
    }
    // Copy items from temp array back to arr
    for (int i = 0; i < n; i++) {
        arr[i] = temp[i];
    }
}

> A small but important trick: k = k % n. If you rotate an array of size 8 by 8, you get the same array back. So rotating by k is the same as rotating by k % n. This saves wasted work when k is large.

This solution is correct, but it always needs a second array of size n. That is O(n) extra space. Can we do better, with no extra array? This is where we ask our two questions.

The key observation: a rotation is three reversals

Here is the clever insight. A left rotation by k is exactly the same as doing three reversals in place:

Reverse the first k items.
Reverse the remaining n - k items.
Reverse the whole array.

Let's watch it happen with 1 2 3 4 5 6 7 8 and k = 4:

start:              1 2 3 4 | 5 6 7 8
reverse first k:    4 3 2 1 | 5 6 7 8
reverse remaining:  4 3 2 1 | 8 7 6 5
reverse the array:  5 6 7 8   1 2 3 4   ✓

The final array is exactly the rotated result — and we never created a second array. Everything happened inside the original arr.

Why does this work? Reversing the two halves puts each group in *backwards* order, and then reversing the whole array flips them back to *forward* order while also swapping the two halves' positions. The two backward flips cancel out the final one, and the net effect is that the front block and back block trade places — which is exactly a rotation.

Where the two-pointer technique fits

Now answer the questions:

Q1: Can we break this into subproblems? Yes — into three "reverse a section" subproblems.
Q2: Can a subproblem be solved with two pointers? Yes — reversing a section is a classic two-pointer task.

To reverse a section, put one pointer at the start and one at the end. Swap the two values, move start forward, move end backward, and stop when they meet in the middle.

void reverse(vector<int> &arr, int start, int end) {
    while (start < end) {
        swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

void kRotations(vector<int> &arr, int k) {
    int n = arr.size();
    k %= n;                    // keep k in range [0, n)
    reverse(arr, 0, k - 1);    // reverse first k
    reverse(arr, k, n - 1);    // reverse the rest
    reverse(arr, 0, n - 1);    // reverse the whole array
}

This version uses O(1) extra space — no temporary array at all — because every swap happens directly inside arr.

The big lesson

The real skill here was not the two-pointer code (that part is short). It was the observation that "rotate the array" can be rebuilt out of "reverse a section." Once you see that, each piece is an easy two-pointer problem, and you stitch their results into the final answer.

When you meet a medium or hard array problem, try asking the same two questions. Sometimes a problem (or even a subproblem) must be *reduced* — reshaped — into a familiar two-pointer pattern before the trick appears.

Spotting a Two-Pointer Subproblem: Rotating an Array Left