Leetcode - Rotate Array Solution

Rotating an array sounds simple enough. Take [1,2,3,4,5,6,7] and rotate it right by 3 positions to get [5,6,7,1,2,3,4]. But here's the thing: there are multiple ways to solve this, and the most elegant solution uses a trick that seems almost too simple once you see it.

The problem asks for an in-place rotation, which means we can't just create a new array. That constraint led me through three different approaches, each teaching me something new about array manipulation.

My First Shot (The Dumb Way)

My first approach was super straightforward but also super inefficient. I just made a copy of the array and put everything where it should go:

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 come on, using an entire new array? That feels like cheating and it's waste of memory. Not ideal for big arrays.

Performance Analysis: Naive Approach

Let me break down the complexity of this straightforward solution:

Time Complexity: O(n)

• I loop through the array twice: once to populate rotated, once to copy back
• Each loop is O(n), so total time is 2 × O(n) = O(n)
• The arithmetic operations and array access are all O(1)

Space Complexity: O(n)

• I create a new array rotated of the same size as the input
• This scales directly with input size - for an array of n elements, I use O(n) extra space
• The copy operation also requires O(n) time

Why this isn't optimal:

• The problem likely expects an in-place solution
• For large arrays, creating a copy doubles the memory usage
• While O(n) time is good, we can achieve the same time with O(1) space

Round Two (Cyclic Approach)

Okay, let's try this again. Instead of making a new array, what if I just moved things around in place? I can use this "cycle" thing where I follow each element to its new spot:

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++;
  }
}

This one is better memory-wise, but honestly, my brain got tangled following the logic. Too many variables floating around.

Performance Analysis: Cyclic Approach

Let me analyze the complexity of this more complex approach:

Time Complexity: O(n)

• I process each element exactly once, even though the while loops look nested
• The outer while (count < n) ensures I visit every element at most once
• Each element is moved to its correct position and never touched again
• The inner while loop follows a cycle until it gets back to the starting position

Space Complexity: O(1)

• I only use a few variables: count, start, current, temp, next, nextTemp
• All of these are single values, not arrays
• No additional data structures that scale with input size

Why it's better than naive:

• Same O(n) time as the naive approach
• Much better O(1) space vs O(n) space of the naive approach
• However, the complexity of the logic makes it hard to get right

The tricky part:

• The while (count < n) loop with the inner while (true) can be confusing
• I had to be very careful about the cycle detection (if (current === start) break)
• One off-by-one error and the whole thing breaks

The Aha Moment (Three-Step Reversal)

Then it just clicked. What if I don't think about moving elements at all? What if I just flip some parts around?

Here's what I did:

1. Flip the whole array
2. Flip just the first k parts
3. Flip the rest

Sounds weird, I know. But check this out with [1,2,3,4,5] rotating by 2:

Flip everything: [5,4,3,2,1] Flip first 2: [4,5,3,2,1] Flip rest: [4,5,1,2,3]

Dang! That's exactly what we wanted. Here's the code:

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--;
  }
}

How This Actually Makes Sense

Here's what's happening in your brain when you rotate right by k: you're taking the last k things and throwing them to the front. But they're backwards. So first flip gets them to the front but wrong order. Second flip fixes that. The middle part is also backwards, so flip three fixes that too.

The best part? It runs in O(n) time and uses basically no extra space. Each element gets touched once, and you just need a couple temp variables.

Performance Analysis: Three-Step Reversal Approach

Let me break down why this approach is optimal:

Time Complexity: O(n)

• I perform exactly three separate reversals, each covering the entire array
• Each reversal iterates through its portion of the array exactly once
• Total operations: n/2 + k/2 + (n-k)/2 = n/2 + n/2 = n operations
• Each element is swapped exactly once per reversal it participates in

Space Complexity: O(1)

• I only use a few variables: start, end, temp (plus n and k for array length)
• All operations are done in-place on the original array
• No additional arrays or data structures created

Why this is the best approach:

1. Optimal time: O(n) is the best we can do since we need to touch each element
2. Optimal space: O(1) means we're not using any extra space proportional to input
3. Simple logic: Just three straightforward reversal loops
4. Easy to understand: The concept is intuitive once you see the pattern

How the time calculation works:

• First reversal: touches n/2 elements (n elements, swapping in pairs)
• Second reversal: touches k/2 elements (k elements, swapping in pairs)
• Third reversal: touches (n-k)/2 elements (n-k elements, swapping in pairs)
• Total: (n + k + n - k)/2 = (2n)/2 = n swaps

Complexity Comparison Summary

Here's how all my approaches stack up:

Approach	Time Complexity	Space Complexity	Code Complexity	Maintainability
Naive (array copy)	O(n)	O(n)	Low	High
Cyclic approach	O(n)	O(1)	Very High	Low
Three-step reversal	O(n)	O(1)	Low	High

Key insights:

1. All approaches achieve optimal O(n) time - you can't rotate an array without looking at each element
2. Only the cyclic and reversal approaches achieve O(1) space - this is usually what interview questions want
3. Three-step reversal hits the sweet spot - optimal time and space with simple, readable code

The three-step reversal approach is the clear winner because it combines:

• Optimal performance (O(n) time, O(1) space)
• Simple, intuitive logic
• Easy to implement and debug
• Code that's easy for others to understand

Let's See It Work

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]

Perfect, works like magic.

Wrap Up

This is one of those problems where the solution seems almost too simple once you see it. I spent way too long on the complicated approaches when the answer was just three simple reversals.

Mess around with it yourself. Try different arrays, different k values. Once you see the pattern, you'll be using this trick everywhere.