Rotate Array

Problem

Given an integer array nums and a non-negative integer k, rotate the array to the right by k positions in place: every element moves k slots toward the end, and elements that fall off the end wrap around to the front. The function returns nothing; it modifies nums directly. Try to do it with O(1) extra space.

• The array is non-empty and has at most 200,000 elements.
• Elements are 32-bit signed integers.
• k is non-negative and may be larger than the array length.

Examples

• nums = [10, 20, 30, 40, 50, 60], k = 2 → [50, 60, 10, 20, 30, 40]. The last two elements move to the front.
• nums = [8, -3, 14, 0, 7], k = 4 → [-3, 14, 0, 7, 8]. Rotating right by 4 on five elements is the same as rotating left by 1.
• nums = [5, 9, 2], k = 5 → [9, 2, 5]. Rotating by 5 is the same as rotating by 5 % 3 = 2.

Hints

1. Rotating by k and rotating by k + n give the same result, so reduce k modulo n first.
2. Building a new array with nums[-k:] + nums[:-k] works but uses O(n) extra space. What in-place operation, applied a few times, could achieve the same rearrangement?
3. Reverse the whole array, then reverse the first k elements, then reverse the remaining n - k.