LeetCode 189 Rotate Array

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].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint:
Could you do it in-place with O(1) extra space?

Diffculty
Easy

Similar Problems

[LeetCode 186] Reverse Words in a String II Medium

Analysis

Solutions

class Solution {
public:
    void rotate(vector<int>& A, int k) {
        int n = A.size();
        if (n <= 0 || k <= 0) return;
        k %= n; // in case k > n
        reverse(A, 0, n - 1);
        reverse(A, 0, k - 1);
        reverse(A, k, n - 1);

        // OR
        // reverse(A, 0, n - k - 1);
        // reverse(A, n - k, n - 1);
        // reverse(A, 0, n - 1);
    }

    void reverse(vector<int>& A, int begin, int end) {
        if (begin >= end) return;
        while (begin < end) {
            swap(A[begin++], A[end--]);
        }
    }
};

Reference