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

TopicDescription
Two PointersScan a sorted array or string from both ends at once to find pairs, remove duplicates, or reverse data in O(n).
Valid PalindromeCheck whether a string reads the same forwards and backwards, ignoring case and punctuation.
Merge Sorted ArrayMerge two sorted arrays into one sorted array in place.
Remove Duplicates from Sorted ArrayRemove duplicate values from a sorted array in place and return the new length.
Move ZeroesMove every zero in an array to the end while keeping the other numbers in order.
Two Sum II - Input Array Is SortedFind two numbers in a sorted array that add up to a target value.