Interview Classic 150 Questions P189 Rotate Array

---

Timeline

Timeline

2025-09-29

init

Reverse Array

---

Problem:

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 a time complexity of O(n), but allocating an extra array also takes time, and the space complexity is also O(n).

#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 approach:
After moving the elements of the array to the right by k positions, the tailk mod nelements will move to the head of the array, and the remaining elements will move to the right 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 elements in the interval [k mod n, n - 1] to get the final answer.

#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

#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());
        }
};