# Summary of solutions in Python

• ## Classical 3-step array rotation:

1. reverse the first n - k elements

2. reverse the rest of them

3. reverse the entire array

``````class Solution(object):
def rotate(self, nums, k):
if k is None or k <= 0:
return
k, end = k % len(nums), len(nums) - 1
self.reverse(nums, 0, end - k)
self.reverse(nums, end - k + 1, end)
self.reverse(nums, 0, end)

def reverse(self, nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start, end = start + 1, end - 1
``````

O(n) in time, O(1) in space

## Rotate `k` times:

Each rotation, we move the `n - 1` to the back of the array one by one and we do rotation `k` times.

``````class Solution(object):
def rotate(self, nums, k):
k = k % len(nums)
for i in xrange(0, k):
tmp = nums[-1]
for j in xrange(0, len(nums) - 1):
nums[len(nums) - 1 - j] = nums[len(nums) - 2 - j]
nums[0] = tmp
``````

O(n^2) in time, O(1) in space

It can't pass the OJ due to TLE.

## Recursive solution

put the shorter part in the correct position then do the rest of them iteratively. This is not necessarily to be a recursive solution.

``````class Solution(object):
def rotate(self, nums, k):
self.helper(0, len(nums) - 1 - (k % len(nums)), len(nums) - 1, nums) # mid belongs to left part

def helper(self, start, mid, end, nums):
left, right = mid - start, end - mid - 1
if left < 0 or right < 0:
return
if left > right:
for j in xrange(mid + 1, end + 1):
nums[j], nums[start] = nums[start], nums[j]
start += 1
self.helper(start, mid, end, nums)
elif right >= left:
i = mid
while i >= start:
nums[i], nums[end] = nums[end], nums[i]
i, end = i - 1, end - 1
if left != right:
self.helper(start, mid, end, nums)
``````

O(n) in time, O(n) in space

## Iterative and improved solution:

put the last `k` elements in correct position (ahead) and do the remaining `n - k`. Once finish swap, the `n` and k decrease.

``````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, k, j = len(nums), k % len(nums), 0
while n > 0 and k % n != 0:
for i in xrange(0, k):
nums[j + i], nums[len(nums) - k + i] = nums[len(nums) - k + i], nums[j + i] # swap
n, j = n - k, j + k
k = k % n
``````

O(n) in time, O(1) in space

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.