How to Rotate Array in C/C++?

Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Pop and Insert

We can loop k times, each time pop an element from the end of array and insert it to the front.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if ((k <= 0) || (nums.size() <= 1)) {
            return;
        }
        k %= nums.size();
        for (int i = 0; i < k; ++i) {
            nums.insert(nums.begin(), nums[nums.size() - 1]);
            nums.pop_back();
        }
    }
}; 

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if ((k <= 0) || (nums.size() <= 1)) {
            return;
        }
        k %= nums.size();
        for (int i = 0; i < k; ++i) {
            nums.insert(nums.begin(), nums[nums.size() - 1]);
            nums.pop_back();
        }
    }
}; 

Make a Copy

If we make a copy of the array, it will become very easy to rearrange the elements without being worried that elements are overwritten.

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> v(nums);
        for (int i = 0; i < nums.size(); ++i) {
            int j = (i + k) % nums.size();
            nums[j] = v[i];
        }
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> v(nums);
        for (int i = 0; i < nums.size(); ++i) {
            int j = (i + k) % nums.size();
            nums[j] = v[i];
        }
    }
};

Please note that we can put the checks on every different solution, in case K is very big compared to the size of the array.

1
2
3
4

if ((k <= 0) || (nums.size() <= 1)) {
    return;
}
k %= nums.size();

if ((k <= 0) || (nums.size() <= 1)) {
    return;
}
k %= nums.size();

Reverse three times

Let’s take [1 2 3 4 5 6 7] and n=7, k=4 for example,
1. Swap first n-k elements, so the index i (0 <= i < n - k) becomes n - k - i. [3 2 1 4 5 6 7]
2. Swap the last k elements, so the index n – k + i (0 <= i < k) becomes n – i.
[3 2 1 7 6 5 4]
3. Swap the entire array, so th index i (0 <= i < n – k) becomes n – (n – k – i) = i + k and the index n – k + i (0 <= i < k) becomes n – (n – i) = i.
[4 5 6 7 1 2 3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if ((k <= 0) || (nums.size() <= 1)) {
            return;
        }
        k %= nums.size();
        if (k > 0) {
            reverse(nums.begin(), nums.begin() + nums.size() - k);
            reverse(nums.end() - k, nums.end());
            reverse(nums.begin(), nums.end());
        }
    }
}; 

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if ((k <= 0) || (nums.size() <= 1)) {
            return;
        }
        k %= nums.size();
        if (k > 0) {
            reverse(nums.begin(), nums.begin() + nums.size() - k);
            reverse(nums.end() - k, nums.end());
            reverse(nums.begin(), nums.end());
        }
    }
}; 

There are other in-place solutions using index pointers, but less intuitive.

–EOF (The Ultimate Computing & Technology Blog) —