# Python O(1) space and O(n) time solution

• 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.

Example:
Input:
[1,2,3,4,5,6]
2

Process:

1. 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]

2. 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
``````

• @zhanchch

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: