Blog

Here’s the question link on LeetCode 189. Rotate Array:

https://leetcode.com/problems/rotate-array/description

Brute Force O(n × k)

The simplest way I can think of is to rotate the array one step at a time.

For every rotation, store the last element, shift everything one position to the right, and put the last element at the beginning.

Repeat this k times.

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

        while(k--) {
            int last = nums[n - 1];

            for(int i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }

            nums[0] = last;
        }
    }
};

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

        while(k--) {
            int last = nums[n - 1];

            for(int i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }

            nums[0] = last;
        }
    }
};

Complexity:

• Time: O(n × k), since we shift almost the entire array for every rotation.
• Space: O(1).

Better O(n)

Wait, why do we need to rotate one step at a time?

We already know where every element needs to go!

If an element is at index i, after rotating right by k steps, its new index will be:

(i + k) % n

So, we can create another array and directly place every element at its correct position.

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

        vector<int> temp(n);

        for(int i = 0; i < n; i++) {
            temp[(i + k) % n] = nums[i];
        }

        nums = temp;
    }
};

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

        vector<int> temp(n);

        for(int i = 0; i < n; i++) {
            temp[(i + k) % n] = nums[i];
        }

        nums = temp;
    }
};

Code lines explained:

• k %= n handles cases where k is greater than the array size.
• (i + k) % n gives us the final position of the current element.
• Store every element at that position in temp.
• Copy the result back into nums.

Complexity:

• Time: O(n).
• Space: O(n), for the temporary array.

Optimal O(n) and O(1) Space

Can we do this without creating another array?

Here’s the interesting part.

Think about the example:

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

We need to move the last 3 elements to the beginning.

What if we reverse the entire array first?

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

Now the elements we need at the beginning are already there, but they’re in the wrong order.

So:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n-k elements.

Let’s see:

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

Reverse all:    [7,6,5,4,3,2,1]

Reverse first 3:[5,6,7,4,3,2,1]

Reverse rest:   [5,6,7,1,2,3,4]

And that’s it!

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

        reverse(nums.begin(), nums.end());

        reverse(nums.begin(), nums.begin() + k);

        reverse(nums.begin() + k, nums.end());
    }
};

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

        reverse(nums.begin(), nums.end());

        reverse(nums.begin(), nums.begin() + k);

        reverse(nums.begin() + k, nums.end());
    }
};

Code lines explained

• k %= n makes sure we’re not rotating more than necessary.
• First, reverse the entire array.
• Then reverse the first k elements to restore their original order.
• Finally, reverse the remaining elements.

Complexity:

• Time: O(n), three reversals.
• Space: O(1), everything happens in-place.