Rotate Array

Problem Statement

Given an array, rotate it to the right by k steps. Modify the array in-place.

Function Signature:

function rotate(arr, k) {
  // Your code here
}

Examples

Input	k	Output
[1, 2, 3, 4, 5, 6, 7]	3	[5, 6, 7, 1, 2, 3, 4]
[-1, -100, 3, 99]	2	[3, 99, -1, -100]
[1, 2]	3	[2, 1]

Constraints

• Array length: 1 ≤ arr.length ≤ 10,000
• Element values: -10⁹ ≤ arr[i] ≤ 10⁹
• k ≥ 0

Interactive Editor

function rotate(arr, k) {
// Your code here

}

Tests: 6 total

Hints

Hint 1: Handle k > length

If k is larger than the array length, rotating by k is the same as rotating by k % arr.length. For example, rotating a 7-element array by 10 is the same as rotating by 3.

Hint 2: Multiple Approaches

There are several ways to solve this:

1. Extra array: Copy elements to their final positions in a new array, then copy back. O(n) space.
2. One by one: Rotate by 1, k times. O(n*k) time.
3. Reversal algorithm: Reverse the whole array, then reverse each part. O(1) space.

The reversal approach is elegant and efficient.

Hint 3: The Reversal Pattern

To rotate [1, 2, 3, 4, 5, 6, 7] right by 3:

1. Reverse the entire array: [7, 6, 5, 4, 3, 2, 1]
2. Reverse the first k elements: [5, 6, 7, 4, 3, 2, 1]
3. Reverse the remaining elements: [5, 6, 7, 1, 2, 3, 4]

The magic: reversing "undoes" the first reversal for each segment, but with the segments swapped.

Hint 4: Why Does Reversal Work?

Think of rotation as moving the last k elements to the front. The reversal algorithm achieves this through a clever trick:

• The full reversal puts the last k elements at the front, but in reverse order
• Reversing just those k elements fixes their internal order
• Reversing the remaining n-k elements fixes their internal order too

Each reversal is O(n), and we do three of them, so total is O(n) time with O(1) space.

Solution

View Solution Explanation

function rotate(arr, k) {
  k = k % arr.length;
  if (k === 0 || arr.length <= 1) return arr;

  reverse(arr, 0, arr.length - 1);  // Reverse all
  reverse(arr, 0, k - 1);            // Reverse first k
  reverse(arr, k, arr.length - 1);   // Reverse rest

  return arr;
}

function reverse(arr, start, end) {
  while (start < end) {
    const temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;
    end--;
  }
}

The Reversal Algorithm

This elegant approach uses three reversals to achieve the rotation:

Step 1: Reverse the entire array

[1, 2, 3, 4, 5, 6, 7] → [7, 6, 5, 4, 3, 2, 1]

Step 2: Reverse the first k elements

[7, 6, 5, 4, 3, 2, 1] → [5, 6, 7, 4, 3, 2, 1]

Step 3: Reverse the remaining n-k elements

[5, 6, 7, 4, 3, 2, 1] → [5, 6, 7, 1, 2, 3, 4]

Why This Works

Imagine the array as two parts: [A][B] where B is the last k elements.

• We want: [B][A]
• Reversing gives: [B_rev][A_rev] (both parts reversed, but in swapped positions)
• Reversing each part individually fixes them: [B][A]

Edge Cases

• k = 0 or k = n: No rotation needed
• k > n: Use k % n to get effective rotation
• n = 1: Single element, no change needed

Alternative Approaches

Extra Array (O(n) space):

function rotate(arr, k) {
  const n = arr.length;
  const result = new Array(n);
  for (let i = 0; i < n; i++) {
    result[(i + k) % n] = arr[i];
  }
  for (let i = 0; i < n; i++) {
    arr[i] = result[i];
  }
  return arr;
}

Simpler to understand but uses extra space.

Complexity: O(n) time, O(1) space (for reversal approach).