Array and Matrix Techniques

The in-place manipulations that come up constantly and are easy to get wrong from memory.

Rotating an array by $k$ — the reversal trick

To rotate a[0..n-1] left by $k$:

void rotateLeft(vector<int>& a, int k) {
    int n = a.size(); k = ((k % n) + n) % n;
    reverse(a.begin(), a.begin() + k);
    reverse(a.begin() + k, a.end());
    reverse(a.begin(), a.end());
}

$O(n)$ time, $O(1)$ extra space. To rotate right by $k$, reverse the whole array first, then the two parts:

Direction	Sequence
Left by $k$	reverse first $k$ → reverse rest → reverse all
Right by $k$	reverse all → reverse first $k$ → reverse rest

Why it works: reversing $AB$ gives $B^R{A}^R$; reversing each part first means the final reversal lands them as $BA$. The identity $(A^R{B}^R{)}^R=BA$ is the whole proof.

The ((k % n) + n) % n guard handles $k>n$ and negative $k$ — both are common in problems and both silently break the naive version.

The cycle-following alternative

The juggling algorithm rotates in place by walking $\gcd (n,k)$ cycles:

for (int s = 0; s < gcd(n, k); s++) {
    int cur = s, val = a[s];
    do {
        int nxt = (cur + k) % n;
        swap(val, a[nxt]);
        cur = nxt;
    } while (cur != s);
}

Same complexity, one pass instead of three, but far worse cache behaviour — the reversal method is usually faster in practice despite doing more total work. See cycle following for the same idea in another setting.

Matrix transformations

All of these are compositions of transpose and reverse:

Transformation	Recipe
Rotate 90° clockwise	transpose, then reverse each row
Rotate 90° counter-clockwise	transpose, then reverse each column (i.e. reverse the row order)
Rotate 180°	reverse row order and reverse each row
Horizontal flip (top ↔ bottom)	reverse the row order
Vertical flip (left ↔ right)	reverse each row
Main-diagonal mirror	transpose
Anti-diagonal mirror	reverse rows → transpose → reverse rows

void rotate90(vector<vector<int>>& m) {
    int n = m.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) swap(m[i][j], m[j][i]);   // transpose
    for (auto& row : m) reverse(row.begin(), row.end());          // reverse rows
}

Derive, don't memorise

Rotate the corner $(0,0)$ in your head and see where it lands. Transpose sends $(i,j)\to (j,i)$; reversing rows sends $(i,j)\to (i,n-1-j)$. Composing gives $(i,j)\to (j,n-1-i)$, which is exactly clockwise rotation. Two seconds of checking beats a memorised table you might have backwards.

Note j = i + 1 in the transpose loop: starting at j = 0 swaps every pair twice, leaving the matrix unchanged. That is one of the most common off-by-one bugs in this code.

Non-square matrices

The in-place trick only works for square matrices. An $r\times c$ matrix rotates into a $c\times r$ one, so allocate:

vector<vector<int>> rotate90(const vector<vector<int>>& m) {
    int r = m.size(), c = m[0].size();
    vector<vector<int>> res(c, vector<int>(r));
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) res[j][r - 1 - i] = m[i][j];
    return res;
}

Other in-place array patterns

Task	Technique
Remove duplicates from a sorted array	two pointers: unique(all(a))
Partition by a predicate	Dutch national flag
Move zeros to the end	a write pointer trailing a read pointer
Reverse in groups of $k$	repeated reverse on subranges
Next lexicographic permutation	next_permutation, or the suffix-scan derivation
Find the missing number in $\mathrm{1..}n$	XOR everything, or sum and subtract
Find a duplicate without extra space	Floyd’s cycle detection on the index graph
Apply a permutation in place	walk its cycles

Traversal orders worth having ready

// spiral traversal
int top = 0, bot = r - 1, lef = 0, rig = c - 1;
while (top <= bot && lef <= rig) {
    for (int j = lef; j <= rig; j++) out.push_back(m[top][j]); top++;
    for (int i = top; i <= bot; i++) out.push_back(m[i][rig]); rig--;
    if (top <= bot) { for (int j = rig; j >= lef; j--) out.push_back(m[bot][j]); bot--; }
    if (lef <= rig) { for (int i = bot; i >= top; i--) out.push_back(m[i][lef]); lef++; }
}

The two guards before the third and fourth loops are essential: without them a single remaining row or column is emitted twice.

Diagonals are indexed by i + j (anti-diagonals, $0$ to $r+c-2$) and by i - j + c - 1 (main diagonals) — a fact that turns many grid DP problems into a one-dimensional sweep.

See also: Prefix Sums · Two Pointers · Sorting · Vectors and Rotations