For each element at position i, we need to move them to (i + k) % n, use a buffer to save the element that has been replaced, and move the replaced element to its right place.
We will start from an element, and mark that, if we come back to the starting point, means we need to start over from the element next of the current starting point.
Work terminates when we have move exactly n times.
startIdx = 0
1, [1,2,3,4,5,6] -> 3, [1,2,1,4,5,6] -> 5, [1,2,1,4,3,6] -> [5,2,1,4,3,6]
startIdx = 1
2, [5,2,1,4,3,6] -> 4, [5,2,1,2,3,6] -> 6, [5,2,1,2,3,4] -> [5,6,1,2,3,4]
class Solution(object): def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ if k == 0: return n = len(nums) k = k % n moves = 0 idx = 0 buff, startIdx = nums[idx], idx # need total of n moves to complete while moves < n: # where the current buffered element should move to idx = (idx + k) % n nums[idx], buff, moves = buff, nums[idx], moves + 1 # we have come back to the start idx, move to process next element if idx == startIdx: idx += 1 if idx >= n: break buff, startIdx = nums[idx], idx
I appreciate your solution - I got stuck on the early loop part for a bit myself (wherein the length of the list is an integer multiple of k) and I now understand the logic for handling that!
One suggestion: remove the
if idx >= n: check - it appears to be superfluous no matter what.
As that last loop check is always hit at least once per list (whether it is needed or not), I thought a check would save a few CPU cycles, so I added it below.
I also have the k==0 check where it can catch k=x*n where x > 0.
class Solution(object): def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ n = len(nums) k %= n if k == 0: return idx = 0 init_idx = idx temp = nums[init_idx] for step in xrange(n): idx = (idx+k)%n nums[idx], temp = temp, nums[idx] if idx == init_idx: # may have hit a cycle so inc idx if step >= n-1: break # we're already done! idx += 1 init_idx = idx temp = nums[idx]