Q189. Rotate Array

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

Follow up:

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

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 <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

The idea is simple, just to keep updating by jumping to new position i <- (i + k) % n. Some minor thing is that we can do k = k % n before getting started. And if k = 0, we can immediately return without doing anything.

The difficulty for me is that I know there will be multiple cycles but it is really hard to know beforehand how many cycles are needed. I was thinking about using a for loop to go through all these cycles in order.

But, such difficulty can be avoided. Or, we don’t need to know the number of cycles beforehand. Instead, we can keep track of the number of positions that have been updated. And whenever we ends one cycle, we can safely go to i <- i + 1 and start a new cycle since we can be sure that it has not been visited. Why? If the next position has been visited by one of the previous ones, no matter which one, we know that the same thing will happen for the next next position as well (since all the previous cycle starts have been visited). Following this, we will have all positions being visited already. So, whenever there is unvisited position, the next position has to be unvisited.

To make this idea more generally, essentially, the strategy here is to come up with an order of visiting (no duplicated visit guaranteed) and visit until we hit all.

Python submission.

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