medium

Rotate Array

Rotate an array to the right by k steps in place.

1. Define the problem

Rotate Array

Given an integer array nums, rotate the array to the right by k steps , where k is non-negative. Do the rotation in place , without allocating extra space for another array. Reverse the whole array, then reverse the first k elements and the remaining n - k elements separately — three reversals, each done with a converging two-pointer swap, together produce the rotation.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -231 ≤ numsi ≤ 231 - 1
  • 0 ≤ k ≤ 105

Example

Inputnums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output[5, 6, 7, 1, 2, 3, 4]

Explanation Reversing the whole array gives [7,6,5,4,3,2,1]; reversing the first 3 elements gives [5,6,7,4,3,2,1]; reversing the remaining 4 elements gives [5,6,7,1,2,3,4].

2. Visualize the solution

Three reversals, each a converging two-pointer swap

Three reversals, each a converging two-pointer swap
Statusinit

k=3 (already less than n=7). Reverse the whole array with converging pointers.

What happens in this step

n = 7, k = 3 % 7 = 3
reverseRange(nums, left=0, right=6)

Before any swaps, the array is [1, 2, 3, 4, 5, 6, 7]. The first reversal will swap elements from both ends inward until left and right meet.
Step 1 of 4

Steps to visualize

  1. Normalize k to k % n, since rotating by the full array length changes nothing.
  2. Reverse the entire array using converging pointers from both ends.
  3. Reverse just the first k elements the same way.
  4. Reverse the remaining n - k elements the same way.
  5. The array is now rotated right by k steps.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Three reversals, each a converging two-pointer swap
Statusinit

k=3 (already less than n=7). Reverse the whole array with converging pointers.

What happens in this step

n = 7, k = 3 % 7 = 3
reverseRange(nums, left=0, right=6)

Before any swaps, the array is [1, 2, 3, 4, 5, 6, 7]. The first reversal will swap elements from both ends inward until left and right meet.
Step 1 of 4
4. Solution

Solution

solution.tsTypeScript
function rotate(nums, k) {
  const n = nums.length;
  const steps = k % n;

  reverseRange(nums, 0, n - 1);
  reverseRange(nums, 0, steps - 1);
  reverseRange(nums, steps, n - 1);

  return nums;
}

function reverseRange(arr, left, right) {
  while (left < right) {
    const temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }
}
Time
O(n)
Space
O(1) (in place, excluding the returned array)
5. Test cases

Test cases

InputExpectedCovers
nums = [1, 2, 3, 4, 5, 6, 7], k = 3[5, 6, 7, 1, 2, 3, 4]example from the docstring
nums = [1, 2], k = 1[2, 1]smallest valid input: only two elements
nums = [1, 2, 3, 4, 5], k = 7[4, 5, 1, 2, 3]k larger than the array length wraps via k % n
nums = [1, 2, 3], k = 0[1, 2, 3]k=0 leaves the array unchanged
nums = [1, 2, 3, 4], k = 4[1, 2, 3, 4]k equal to the array length is a full rotation, unchanged
nums = [1], k = 5[1]a single-element array is unaffected by any k

Keep reading