LeetCode Solution: 189. Rotate Array

Unlocking Array Rotation: The Elegant Three-Reversals Trick (LeetCode 189)

Hey there, fellow coders! 👋 Vansh here, ready to tackle another classic LeetCode challenge that's as tricky as it is insightful: Rotate Array. Don't let the "medium" difficulty label scare you off! We're going to break it down, build up our intuition, and master an incredibly elegant solution that's a true interview favorite.

Imagine you have a deck of cards, and you want to move some cards from the end to the beginning. That's essentially what we're doing here! Let's dive in!

---

🚀 Problem Explanation: The Rotating Challenge

The problem, 189. Rotate Array, asks us to take an array of numbers (nums) and rotate it to the right by k steps. What does "rotate to the right" mean? It means the elements from the end of the array move to the front, pushing everything else further right.

Let's look at an example to make it super clear:

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

• Rotate 1 step right: The 7 moves to the front. [7, 1, 2, 3, 4, 5, 6]
• Rotate 2 steps right: The 6 (which was originally 7's neighbor) moves to the front, 7 shifts right. [6, 7, 1, 2, 3, 4, 5]
• Rotate 3 steps right: The 5 moves to the front. [5, 6, 7, 1, 2, 3, 4]

Output: [5, 6, 7, 1, 2, 3, 4]

Notice how the last k elements (5, 6, 7 in this case) end up at the beginning, in their original relative order. The first n-k elements (1, 2, 3, 4) follow them, also in their original relative order.

Important Note: k can be larger than the array's length (n). If k = 8 for an array of size 7, it's effectively rotating 1 step (8 % 7 = 1). So, we'll always want to use k % n to get the effective number of rotations.

The follow-up question is key: Can we do it in-place with O(1) extra space? This is where the magic happens! ✨

---

🤔 Intuition: The "Aha!" Moment with Reversals

Initially, you might think of shifting elements one by one, or perhaps copying parts to a temporary array. While these work, they either exceed the time complexity (O(N*k) for shifting) or space complexity (O(N) for temporary array) requirements for the "optimal" solution.

So, how do we achieve O(1) space? We need to manipulate the array itself. This often points to using operations like swapping or reversing.

Let's revisit our example: [1, 2, 3, 4, 5, 6, 7], k = 3
Desired Output: [5, 6, 7, 1, 2, 3, 4]

Notice that the array is essentially split into two parts:

1. The last k elements: [5, 6, 7]
2. The first n-k elements: [1, 2, 3, 4]

And the final array is [last k elements] + [first n-k elements].

This is where the "Three Reversals" trick shines! It's a bit counter-intuitive at first, but incredibly powerful.

Imagine this:

1. If we reverse the entire array:
   [1, 2, 3, 4, 5, 6, 7] becomes [7, 6, 5, 4, 3, 2, 1]
   Now, the elements that should be at the front (5, 6, 7) are actually at the beginning of the reversed array, but in reversed order (7, 6, 5). And the elements that should be at the end (1, 2, 3, 4) are at the end, also reversed (4, 3, 2, 1).

2. What if we reverse just the first k elements (which are 7, 6, 5)?
   [7, 6, 5] becomes [5, 6, 7].
   Our array is now [5, 6, 7, 4, 3, 2, 1]. Looking good for the first part!

3. Finally, what if we reverse the remaining n-k elements (which are 4, 3, 2, 1)?
   [4, 3, 2, 1] becomes [1, 2, 3, 4].
   Our array is now [5, 6, 7, 1, 2, 3, 4].
   🎉 Voila! This is exactly our desired output!

This three-step reversal magically puts everything in its correct place without needing any extra space.

---

🧠 Approach: Step-by-Step with the Three Reversals

Let's formalize the steps for our example nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

1. Normalize k: Calculate k = k % n.

   • n (size of nums) = 7.
   • k = 3 % 7 = 3. (If k was, say, 10, it would be 10 % 7 = 3).

2. Reverse the entire array: Reverse all elements from index 0 to n-1.

   • [1, 2, 3, 4, 5, 6, 7]
   • After reversing: [7, 6, 5, 4, 3, 2, 1]

3. Reverse the first k elements: Reverse elements from index 0 to k-1.

   • k = 3, so we reverse [7, 6, 5]
   • [7, 6, 5] becomes [5, 6, 7]
   • Array is now: [5, 6, 7, 4, 3, 2, 1]

4. Reverse the remaining n - k elements: Reverse elements from index k to n-1.

   • n - k = 7 - 3 = 4, so we reverse [4, 3, 2, 1]
   • [4, 3, 2, 1] becomes [1, 2, 3, 4]
   • Array is now: [5, 6, 7, 1, 2, 3, 4]

And that's it! This approach is elegant, efficient, and perfectly satisfies the problem's constraints.

---

💻 Code: C++ Implementation

Here's the C++ code that implements this "Three Reversals" strategy. We'll use the standard library's std::reverse function, which makes it incredibly concise.

#include <vector> // Required for std::vector
#include <algorithm> // Required for std::reverse

class Solution {
public:
    void rotate(std::vector<int>& nums, int k) {
        int n = nums.size();

        // Step 1: Normalize k
        // If k is greater than the array size, or k is negative (though problem says non-negative),
        // we take its modulus with n to get the effective number of rotations.
        // E.g., k=8 for n=7 is same as k=1 (8 % 7 = 1).
        k %= n;

        // Step 2: Reverse the entire array
        // Example: [1, 2, 3, 4, 5, 6, 7] -> [7, 6, 5, 4, 3, 2, 1]
        std::reverse(nums.begin(), nums.end());

        // Step 3: Reverse the first k elements
        // This part corresponds to the elements that should move to the front.
        // In our example, k=3, so we reverse [7, 6, 5] -> [5, 6, 7]
        // Array becomes: [5, 6, 7, 4, 3, 2, 1]
        std::reverse(nums.begin(), nums.begin() + k);

        // Step 4: Reverse the remaining (n - k) elements
        // This part corresponds to the elements that should follow.
        // In our example, n-k=4, so we reverse [4, 3, 2, 1] -> [1, 2, 3, 4]
        // Array becomes: [5, 6, 7, 1, 2, 3, 4] - The final rotated array!
        std::reverse(nums.begin() + k, nums.end());
    }
};

---

📊 Time & Space Complexity Analysis

Let's break down how efficient this approach is:

• Time Complexity: O(N)

  • n = nums.size(): O(1)
  • k %= n;: O(1)
  • std::reverse(nums.begin(), nums.end()): Reversing the entire array of N elements takes O(N) time.
  • std::reverse(nums.begin(), nums.begin() + k): Reversing k elements takes O(k) time.
  • std::reverse(nums.begin() + k, nums.end()): Reversing N-k elements takes O(N-k) time.
  • In total, O(N) + O(k) + O(N-k) = O(2N), which simplifies to O(N). We touch each element a constant number of times.

• Space Complexity: O(1)

  • We are modifying the nums array directly (in-place).
  • We are not using any auxiliary data structures (like a new array) whose size grows with N.
  • Therefore, the extra space used is constant, making it O(1).

This solution successfully addresses the "Follow up" question! 🚀

---

🌟 Key Takeaways

• Normalize k: Always handle k values greater than n by taking k % n. This prevents unnecessary rotations and ensures correctness.
• The Power of reverse: Sometimes, a sequence of seemingly simple operations like reverse can achieve complex transformations very elegantly and efficiently. Look for opportunities to break down a problem into inversions or rearrangements.
• In-Place Solutions: Competitive programming and interviews often favor solutions that minimize extra space. The "Three Reversals" method is a prime example of an O(1) space, in-place solution.
• Think Outside the Box: If your first few ideas are too slow or use too much space, consider alternative ways to manipulate data, even if they seem unconventional at first.

This problem is a fantastic way to stretch your thinking beyond brute-force and learn a valuable pattern. Keep practicing, and you'll find these "aha!" moments more and more often!

---

Author: Vansh2710 | Published: 2026-03-26 01:07:27