Leetcode 150 | Day 6: Rotate Array – Naive vs. Optimized

## Leetcode 189: Rotate Array

Leetcode 189 asks us to rotate an array by k steps, where k is non-negative. Here's a concrete example:

Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 2
Output: [6, 7, 1, 2, 3, 4, 5]

All we're doing is taking the last k values of the array and moving them to the front. Simple enough when k is smaller than the array length - but once k exceeds the length, it's not quite as straightforward an explanation, even though the effect is still exactly the same. More on that in a moment.

I found this problem to be both cumbersome to understand and glaringly obvious once you do - particularly the optimized approach.

---

Approach 1: Naive (Slice)

This approach uses .slice() and a simple for loop to achieve our objective. It's considerably more straightforward than the optimized approach later in this article, but we do sacrifice a little for that simplicity.

Here's how it works:

First we normalize k. This step is necessary in both approaches - it's possible someone may pass in a k value larger than nums.length, so k needs to be accounted for before we do anything else. k is normalized before we do anything else - here's why.

Next, we call .slice() twice.

First call to .slice():

const end = nums.slice(nums.length - k); // [6, 7]

We call .slice() on nums and pass in the expression nums.length - k. This creates a brand new array containing everything from that index to the end of nums. nums itself is not touched.

Using our example:

nums = [1, 2, 3, 4, 5, 6, 7]
nums.length = 7
k = 2
7 - 2 = 5

So we start at index 5, which is the element 6, and grab everything from there to the end. end is now a new array: [6, 7].

Second call to .slice():

const start = nums.slice(0, nums.length - k); // [1, 2, 3, 4, 5]

Same idea, but this time we isolate everything that comes before index k. start is now a new array: [1, 2, 3, 4, 5]. Again, nums is still untouched.

Combining the two:

const rotated = [...end, ...start]; // [6, 7, 1, 2, 3, 4, 5]

We use the spread operator to combine end and start into a third new array in the correct rotated order.

This is directly related to what makes this approach naive by comparison. Both calls to .slice() each produce a new array, and rotated is a third. All of that lives in memory for the duration of the function, which gives us a space complexity of O(n).

Writing the result back to nums:

for (let i = 0; i < nums.length; i++) {
    nums[i] = rotated[i];
}

We iterate through nums and overwrite each element with the corresponding value from rotated. This is necessary because the problem requires us to modify nums in place - we can't just return a new array.

---

Approach 2: Optimized (Three-Reverse / In-Place)

To explain how this approach works, I think it makes the most sense to start with the helper function, reverse().

The function signature:

function reverse(nums, start, end)

• nums - the array we are reversing
• start - the index where the reversal begins
• end - the index where the reversal ends Worth noting: this function doesn't reverse the entire array by default. It reverses whatever section you point it at, defined by start and end. That's what makes it useful here - we call it three times, each time targeting a different section.

---

The while loop

Once inside the function, we enter a while loop with the condition while (start < end).

I had a hard time visualizing this one. For those who appreciate being able to build a mental model before moving on, here's a step-by-step walkthrough showing what happens on each iteration - and what eventually terminates the loop.

Step 1

Step 2

Step 3

Step 4

While start is less than end, we do three things:

1. We create a variable called temp and assign it the value at nums[start] - whatever start is pointing to in the current iteration. We do this to preserve that value, otherwise it gets overwritten in the next step.
2. We assign the value at nums[end] to nums[start].
3. We assign the value stored in temp to nums[end]. That's the swap. The final two steps are to increment start and decrement end, then the loop checks start < end again and either continues or stops.

Normalizing k

Back in rotate(), the first line of logic is:

k = k % nums.length;

At first glance this is easy to blow past. It's doing more work than it looks like.

What if someone passes in k = 10 on a 7-element array? What does rotating by 10 even mean? You could move the last element to the front 10 times - but after 7 moves, you're back to the exact same array you started with. Those 7 moves were completely wasted.

k = 10 % 7 = 3

So k becomes 3. If 7 of those moves cancelled out, that means only 3 were actually meaningful. This line throws away the full loops and keeps only the remainder — the part that actually changes anything. When k is already smaller than nums.length, the mod is a no-op and k stays the same.

---

The three calls to reverse()

Call 1:

reverse(nums, 0, nums.length - 1);

• 0 - start at the beginning
• nums.length - 1 - end at the last index
• Reverses the entire array

The entire array is now flipped. The last 2 elements (6 and 7) are at the front but in the wrong order, and (1, 2, 3, 4, 5) are at the back, also in the wrong order. The next two calls fix both halves.

---

Call 2:

reverse(nums, 0, k - 1);

• 0 - start at the beginning
• k - 1 - if k = 2, this is index 1. Arrays are 0-based, so this covers exactly the first k elements.
• Reverses the first k elements only

The first 2 values are now correct. The last 5 are still wrong.

Call 3:

reverse(nums, k, nums.length - 1);

• k - start at index 2, right after the section we just fixed
• nums.length - 1 - end at the last index
• Reverses the remaining portion of the array

Done. 6 and 7 are in the correct order at the front, and the remaining 5 values have been corrected behind them. That's a right rotation by k = 2.

Conclusion

I think there's a real case to be made for either approach depending on the size of the dataset you're working with. Both have the same time complexity - O(n) - a result of the for loop in the naive approach and the three reversal passes in the optimized approach, each of which touches every element. The difference is space. The naive approach comes in at O(n) because of the additional arrays it creates. The optimized approach is O(1) - our reverse() helper does everything directly inside nums, so no extra memory is allocated regardless of input size.

My honest take: if you're working with datasets that are limited in size, go for readability and use the naive approach. Just know going in that it won't scale the way the optimized approach will.

Comments

[speed engineer]

Really clean writeup - the k %= n normalization is the line most people blow right past, so glad you gave it its own section.

One intuition that makes the three-reverse click: a right rotation is just "reverse the whole thing, then un-reverse each piece." If the array is A followed by B and you want B followed by A, reversing everything gives you B-reversed followed by A-reversed, and the two inner reversals flip each block back to forward order. So it isn't three arbitrary passes - it's one structural identity.

Two follow-ups worth having ready, since interviewers love pushing on this one:

• "Now make it a LEFT rotation by k." Same helper - reverse the first k and the rest, then reverse the whole array (equivalently, rotate right by n - k). Naming that transform shows you understood the structure, not just memorized the three calls.
• "Any other O(1)-space way?" The cyclic-replacement (juggling) method is also O(n) time / O(1) space - you walk element cycles, and GCD(n, k) tells you how many. Fiddlier to get right, but good to name so you're not caught flat.

Agree both are legit to show; the real signal is stating the space trade out loud and handling k = 0 / empty input, which you did.