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 nums = [1,2,3,4,5,6,7], k = 3 case, we can find the resulting array [5,6,7,1,2,3,4] can be splitted into two parts: [5,6,7] and [1,2,3,4], and the first part is having a length of 3 which is k, and each part is preseving the same order. We can rotate the array from any splice easily (using the standard libary 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 the auxiliary array to placehold the reverse

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 implementaton 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);
        }
    }
}

---

Last update: April 1, 2022