Rotate an array k positions to the right, in place.

Settle the specification first

Two things in the problem statement are genuinely ambiguous and both change the code. "Rotate right by k" usually means the element at index i moves to index (i + k) mod n, so the tail wraps around to the front, but plenty of interviewers mean the opposite and a left rotation by k is a right rotation by n - k. Ask, then say your convention out loud so a disagreement surfaces before you have written thirty lines against the wrong one.

The second is the range of k. If k can be larger than the array, every index expression needs a modulo; if k can be negative, the modulo needs correcting because in Java, C and C++ the remainder of a negative operand is negative. k = ((k % n) + n) % n handles both and is two characters longer than the version that does not. An empty array makes k % n a division by zero, so it gets its own guard.

Why three reversals work

The copy-to-a-new-array solution is O(n) time and O(n) space, and it is worth saying that it is perfectly acceptable in most real code before you are asked for the in-place version. The interesting version is the one that uses a constant amount of extra memory.

Think of the rotated result as two blocks that have swapped places. The array is A followed by B, where B is the last k elements, and the answer is B followed by A. Reversing the whole array gives you reverse(B) followed by reverse(A) — the blocks are now in the order you want, each internally backwards. Reversing each block in place undoes that, and the block boundaries are known because reverse(B) occupies exactly the first k slots.

void rotate(int[] a, int k) {
    int n = a.length;
    if (n == 0) return;
    k = ((k % n) + n) % n;          // survives k > n and negative k

    reverse(a, 0, n - 1);           // now reverse(B) ++ reverse(A)
    reverse(a, 0, k - 1);           // restore B
    reverse(a, k, n - 1);           // restore A
}

private void reverse(int[] a, int i, int j) {
    while (i < j) {
        int t = a[i];
        a[i++] = a[j];
        a[j--] = t;
    }
}

Saying "reverse all, reverse the two parts" is not an explanation, and an interviewer who has heard it fifty times will ask why it works. The block argument above is the answer, and it takes fifteen seconds.

Cost: the first reversal performs n/2 swaps and the two partial reversals perform k/2 and (n-k)/2, which sum to another n/2. That is n swaps and therefore 2n element writes, all O(n) time with O(1) auxiliary space. The k = 0 case needs no branch: reverse(a, 0, -1) does nothing because the loop condition fails immediately, and reversing the whole array twice is the identity.

The alternative that touches each element once

If the 2n writes bother you, there is a version that performs exactly n. Follow the permutation directly: carry the value from index start, drop it at (start + k) mod n, pick up whatever was there, and continue until you return to start.

void rotate(int[] a, int k) {
    int n = a.length;
    if (n == 0) return;
    k = ((k % n) + n) % n;
    if (k == 0) return;

    int moved = 0;
    for (int start = 0; moved < n; start++) {
        int current = start;
        int carried = a[start];
        do {
            int next = (current + k) % n;
            int displaced = a[next];
            a[next] = carried;      // drop what we are holding
            carried = displaced;    // and pick up what it evicted
            current = next;
            moved++;
        } while (current != start);
    }
}

The outer loop exists because one cycle does not necessarily cover the array. Stepping repeatedly by k modulo n visits exactly n / gcd(n, k) distinct positions before returning to the start, so the permutation decomposes into gcd(n, k) separate cycles and you need one pass per cycle. With n = 6, k = 2 the gcd is 2 and you get the even indices and the odd indices as two disjoint cycles; a single loop from index 0 would finish having rotated only half the array. The moved counter is what makes the outer loop terminate at the right point without computing the gcd explicitly, though computing it and looping start from 0 to gcd - 1 is equally correct and arguably clearer.

Where this goes wrong under pressure

The costliest failure is the missing k %= n, because it is not a wrong answer on one edge case — with k larger than n the reversal version indexes past the end and the cyclic version spins. Candidates write it correctly for k of 3 against 7 elements and never test k of 7 or 10.

Then be honest about what in-place buys. It is O(1) auxiliary space, which is a real distinction from the buffer version, but mutating an array that other code holds a reference to is a semantic change rather than an optimisation. The request for constant space is a test of your index arithmetic, not a claim that mutation is better engineering.

And where rotations are frequent and the array is rarely read in full, neither algorithm is right: store a logical offset and add it modulo n on each access, making a rotation an O(1) update to one integer.