Rotate array by k

Rotate an array right by k positions in place using three reversals instead of a second array.

The idea

Rotating right by k moves the last k elements to the front. Reversing the whole array puts every element backward, including those two groups; reversing each group on its own then un-reverses it, leaving both groups internally correct and in the right place.

Code

public static void Rotate(int[] a, int k) {
    k %= a.Length;
    Reverse(a, 0, a.Length - 1);
    Reverse(a, 0, k - 1);
    Reverse(a, k, a.Length - 1);
}

static void Reverse(int[] a, int l, int r) {
    while (l < r) { (a[l], a[r]) = (a[r], a[l]); l++; r--; }
}

Tips

• k %= a.Length first: rotating by the array length, or a multiple of it, changes nothing.
• Three reversals touch every element a constant number of times, so this beats the extra-array version on space without giving up O(n) time.

In the .NET library

The simplest correct version copies into a new array at (i + k) % n and copies back - O(n) space but easier to get right under pressure; reach for the reversal trick once that version is comfortable.