Cover image for Interview Classic 150 Questions P189 Rotate Array

Interview Classic 150 Questions P189 Rotate Array

(Updated: )
algorithm
, ,
Timeline

Timeline

2025-09-29

init

Reverse Array

Title:

P189 Rotate Array

https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150

Using an extra array. This method has time complexity O(n), but creating an extra array also takes time and space complexity O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>

using std::vector;

class Solution {
public:
  void rotate(vector<int> &nums, int k) {
    int n;
    int tmp;
    int pos;

    n = nums.size();
    vector<int> vec(n);

    for (int i = 0; i < n; i++) {
      pos = (i + k) % n;
      vec[pos] = nums[i];
    }
    nums = std::move(vec);
  }
};

Another clever method:
After moving the elements of the array to the right by k times, the tailk mod nelements will move to the head of the array, and the remaining elements will move backward by k mod n positions.

This method is array reversal: we can first reverse all elements, so that the tailk mod nelements are moved to the head of the array, then we reverse the elements in the interval [0, k mod n - 1] and the interval [k mod n, n - 1] to get the final answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <algorithm>
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();

        k %= n;

        std::reverse(nums.begin(), nums.begin() + n - k);
        std::reverse(nums.begin() + n - k, nums.end());
        std::reverse(nums.begin(), nums.end());

    }
};

leetcode hot 100 rewrite

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector>
#include <algorithm>

using std::vector;

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

                k = k % n;

                std::reverse(nums.begin(), nums.begin() + n - k);
                std::reverse(nums.begin() + n - k, nums.end());
                std::reverse(nums.begin(), nums.end());
        }
};