Rotate Array

Medium· reversal· in-place

Problem

Rotate an array to the right by k steps, so that each element moves k positions forward and elements that fall off the end wrap around to the front. k can be larger than the array length. Try to do it in place with O(1) extra space.

Examples

Input: nums = [1,2,3,4,5,6], k = 2

Output: [5,6,1,2,3,4]

The last two elements wrap around to the front.

Input: nums = [7,8], k = 3

Output: [8,7]

Rotating by 3 is the same as rotating by 3 % 2 = 1.

Constraints

• 1 <= nums.length <= 10^5
• 0 <= k <= 10^5

Hints & approach

Hint 1

First reduce k modulo the length.

Hint 2

Look at where the last k elements end up compared with the rest.

Hint 3

Reversing the whole array and then reversing two pieces separately puts everything in place.

Approachtry the hints first

Set k = k % n. Reverse the entire array, which brings the last k elements to the front but in reversed order. Then reverse the first k elements and the remaining n - k elements individually to restore their internal order. Three reversals touch each element a constant number of times and need no extra buffer.

Time O(n) · Space O(1)

← PreviousCheck if Array Is Sorted and Rotated Next →Product of Array Except Self