How does the three-reversal trick rotate an array by k positions in place?

## The trick To rotate an n-element array right by k (the last k entries move to the front, the rest shift back), do three range reversals: 1. `reverse(a, 0, n-1)` — the whole array 2. `reverse(a, 0, k-1)` — the first k entries 3. `reverse(a, k, n-1)` — the remaining n-k entries Nothing else. No second array, no shifting loop. ## Why it works — the block identity View the array as the concatenation of two blocks: `X` of length n-k and `Y` of length k, so the array is `X Y`. A right rotation by k is exactly `Y X`. The identity that drives everything is: **reversing a concatenation reverses the blocks and swaps their order.** Formally, `reverse(X Y) = reverse(Y) reverse(X)`. So step 1 produces `reverse(Y) reverse(X)`. The blocks are now in the order you want — `Y`'s material before `X`'s — but each is internally backwards. Step 2 reverses the first k slots, which hold `reverse(Y)`, restoring `Y`. Step 3 reverses the last n-k slots, which hold `reverse(X)`, restoring `X`. The result is `Y X`. ## A trace worth memorising An on-call roster `[A, B, C, D, E]` rotated right by k = 2 should become `[D, E, A, B, C]` — the last two weeks move to the front. - After reversing everything: `[E, D, C, B, A]` - After reversing the first 2: `[D, E, C, B, A]` - After reversing the last 3: `[D, E, A, B, C]` Doing the three reversals in the other order — first k, then the rest, then the whole array — gives a *left* rotation by k. Both orderings are correct algorithms for different conventions, which is why an interviewer will ask which direction yours produces. Always state the convention before you write. ## The failure this question hunts for The k values that break naive code are the ones outside `[0, n)`. - **k >= n.** `reverse(a, 0, k-1)` walks its right pointer to index k-1, which is past the last element. Depending on the environment that is a crash or silent corruption of neighbouring memory. Fix it before the first reversal: `k = k mod n`. - **k = 0 or k = n.** After reduction both mean "do not move anything", and the trick handles them correctly *if* your range reversal is a no-op on an empty or single-element range. With k = 0, step 2 gets the empty range `[0, -1]` and step 3 undoes step 1. With k = n before reduction, step 2 reverses everything back and step 3 gets the empty range `[n, n-1]`. Neither needs a special case; both need a range reversal that checks `lo < hi` rather than assuming a non-empty range. - **Negative k**, if your interface allows a rotation the other way, needs normalising with `k = ((k mod n) + n) mod n`, because a plain remainder can stay negative. ## Cost, precisely Each element is written exactly twice: once by the full reversal, once by whichever partial reversal covers its new home. That is 2n writes, or n swaps, across three passes. Time is O(n) and auxiliary space is O(1) — the reversals need only their two indices and a swap temporary. Compare the obvious alternatives. Copying into a fresh array of size n and reading back is O(n) time but O(n) extra space, and for a large array that means doubling peak memory. Rotating by repeated single-position shifts is O(n) space-free but O(n*k) time, which becomes quadratic when k grows with n. The three-reversal trick is the one that is linear in time *and* constant in extra space, which is precisely the pair of constraints interviewers set up when they say "in place". ## Why it survives contact with real hardware All three passes are two-pointer scans converging from the ends of a contiguous range, so every touch is sequential and predictable. That is why the trick remains the default even though it writes each element twice: the write count is not the binding cost on large data, the memory access pattern is. The same reason makes it easy to reason about in review — three calls to a primitive you already trust, with no index arithmetic to get subtly wrong beyond the modulo.