Leetcode - Rotate Array Solution

Rotating an array means moving the last k values to the front. For example, rotating [1,2,3,4,5,6,7] right by 3 produces [5,6,7,1,2,3,4]. The challenge is doing that in place, without a second array.

I compared a copy based solution, a cyclic solution, and the three step reversal. The first two clarify the constraints. I would keep the reversal version.

A baseline with a copy

My first approach placed every value in a new array and copied the result back:

function rotateNaive(nums, k) {
  const n = nums.length;
  if (n <= 1) return nums;

  k = k % n;
  const rotated = new Array(n);

  // Just put each element where it should go
  for (let i = 0; i < n; i++) {
    rotated[(i + k) % n] = nums[i];
  }

  // Copy back to original
  for (let i = 0; i < n; i++) {
    nums[i] = rotated[i];
  }
}

It works, but the rotated array costs O(n) extra space. Both passes are linear, so the time complexity is O(n), but the additional array is unnecessary when the problem requires an in place result.

I loop through the input once to fill rotated and once more to copy it back. The arithmetic and array access are O(1), so the total time remains O(n). The extra array is the limiting cost: it grows with n.

Cyclic in place attempt and cost

I then tried moving each value directly to its destination by following rotation cycles:

function rotateCyclic(nums, k) {
  const n = nums.length;
  if (n <= 1) return nums;

  k = k % n;
  let count = 0;
  let start = 0;

  while (count < n) {
    let current = start;
    let temp = nums[start];

    // Follow the rotation cycle
    while (true) {
      const next = (current + k) % n;
      const nextTemp = nums[next];
      nums[next] = temp;
      temp = nextTemp;
      current = next;
      count++;

      if (current === start) break;
    }

    start++;
  }
}

The cyclic version uses O(1) extra space and still touches each element once. I found the control flow harder to follow. The while (count < n) loop surrounds a while (true) loop. Each cycle ends when if (current === start) break runs. The variables count, start, current, temp, next, and nextTemp are all constant sized, but one off by one error can corrupt the result.

The outer while (count < n) ensures that the total number of moves is linear. The cycle logic thus takes O(n) time and O(1) extra space, but its correctness is less obvious than the reversal approach.

Three reversals

The simpler in place idea is to reverse the whole array, reverse the first k values, and reverse the remaining values. For [1,2,3,4,5] rotated right by 2:

[5,4,3,2,1] after reversing everything, [4,5,3,2,1] after reversing the first two values, and [4,5,1,2,3] after reversing the rest.

That sequence puts the original last k values at the front and restores their order:

function rotate(nums, k) {
  const n = nums.length;
  if (n <= 1) return nums;

  k = k % n;
  if (k === 0) return nums;

  // Step 1: Flip entire array
  let start = 0;
  let end = n - 1;
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }

  // Step 2: Flip first k elements
  start = 0;
  end = k - 1;
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }

  // Step 3: Flip remaining n-k elements
  start = k;
  end = n - 1;
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
}

Right rotation takes the final k values and moves them before the first n-k values. The full reversal exchanges the positions of the two groups and reverses the order within each group. Reversing each group separately fixes the order within the groups.

The three loops perform at most n/2 + k/2 + (n-k)/2 = n swaps. With integer loop bounds, the exact count is floor(n/2) + floor(k/2) + floor((n-k)/2), and it remains O(n). The algorithm stores only start, end, temp, n, and k. Thus, it uses O(n) time and O(1) extra space. It touches the original array only.

Reversal cost and comparison

The three implementations compare as follows:

All three approaches take O(n) time. The copy version uses O(n) space, while the cyclic and reversal versions use O(1). I prefer the reversal because its state is limited to a few indices and the three operations are easy to inspect.

Example and conclusion

const nums = [1, 2, 3, 4, 5, 6, 7];
console.log("Before:", nums);
rotate(nums, 3);
console.log("After:", nums); // [5, 6, 7, 1, 2, 3, 4]

The example produces [5, 6, 7, 1, 2, 3, 4] in place.

The copy and cyclic versions make the space constraint visible, but three reversals meet the constraint with simpler control flow. The key is to reverse the complete array first and then restore the order of the two resulting groups.