0189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Analysis

This question can be solved by just observing the pattern:

For the nums = [1,2,3,4,5,6,7], k = 3 case, we can find that the resulting array [5,6,7,1,2,3,4] can be split into two parts: [5,6,7] and [1,2,3,4], and the first part has a length of 3, which is k, and each part preserves the same order. We can rotate the array from any splice easily (using the standard library std::reverse is easy), so we can think of using the reverse way to slice our array into two parts:

1. reverse the entire array so we can choose where to split the two parts
2. reverse the first part so we can get the first part in increasing order

3. reverse the second part so we can get the second part in increasing order

4. Time: $O(n + k + n - k)$ = $O(n)$

5. Space: $O(1)$ – we don't need an auxiliary array to hold the reversed values

Code

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

STL implementation of reverse

STL doesn't require an aux array to swap, ref: https://en.cppreference.com/w/cpp/algorithm/reverse

template<class BidirIt>
constexpr // since C++20
void reverse(BidirIt first, BidirIt last)
{
    using iter_cat = typename std::iterator_traits<BidirIt>::iterator_category;

    // Tag dispatch, e.g. calling reverse_impl(first, last, iter_cat()),
    // can be used in C++14 and earlier modes.
    if constexpr (std::is_base_of_v<std::random_access_iterator_tag, iter_cat>) {
        if (first == last)
            return;
        for (--last; first < last; (void)++first, --last) {
            std::iter_swap(first, last);
        }
    }
    else {
        while ((first != last) && (first != --last)) {
            std::iter_swap(first++, last);
        }
    }
}