189. Rotate Array - cocoder39/coco39_LC GitHub Wiki

189. Rotate Array

Notes 2020:

Option 1: reverse 3 times

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        
        def reverse_helper(begin, end):
            while begin < end:
                nums[begin], nums[end] = nums[end], nums[begin]
                begin += 1
                end -= 1
        
        reverse_helper(0, n-k-1)
        reverse_helper(n-k, n-1)
        reverse_helper(0, n-1)

Option 2: keep swapping

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        
        start = count = 0
        while count < n:
            cur, prev = start, nums[start]
            while True:
                next_idx = (cur+k) % n
                nums[next_idx], prev = prev, nums[next_idx]
                cur = next_idx
                count += 1
                
                if cur == start:
                    break
            start += 1

One concern is if start+1 points to an index that falls into previous cycle. Proof by contradiction: if start+1 falls into a previous cycle, then start+1 + 1 should also fall into the exact same cycle so every element falls into the cycle. If so, count should be already n so there is no need to kick off a new cycle.

================================================================

solution 1: three-way rotation, O(n) time and O(1) space

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int sz = nums.size();
        k %= sz;
        reverse(nums, 0, sz - k - 1);
        reverse(nums, sz - k, sz - 1);
        reverse(nums, 0, sz - 1);
    }
private:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start++], nums[end--]);
        }
    }
};

solution 2 : O(n) time and O(n) space

void rotate(vector<int>& nums, int k) {
        vector<int> copy = nums;
        int sz = nums.size();
        for (int i = 0; i < sz; i++) {
            nums[(i + k) % sz] = copy[i];
        }
    }
⚠️ **GitHub.com Fallback** ⚠️