LeetCode #189 Medium

Rotate Array

Rotate an array to the right by k steps, in place.

arraytwo-pointersin-place
Open on LeetCode ↗
02

Intuition

💡

Before any of the clever part, handle the thing that breaks most submissions: k can exceed n. Rotating by n returns the array to itself, so without k %= n you either index out of bounds or grind through pointless work. Once that is out of the way, the reversal algorithm is the trick worth memorising — reverse the whole array, then the first k, then the rest. The full reverse puts the right block in front but backwards; the two local reversals straighten each one out. Three linear passes, O(1) space, no temporary array.

03

Approach

1

Reduce k first

Rotating by n returns the array to itself, so take k %= n. Skipping this either indexes out of bounds or does needless work, and it is the most common bug in the reversal version. If k becomes 0, there is nothing to do.

2

Reverse the whole array

After a full reverse, the block that should end up at the front is at the front — but reversed — and the block that should follow is behind it, also reversed. The relative arrangement of the two blocks is now correct even though their internal orders are not.

3

Reverse each block back

Reverse [0, k) and then [k, n). Each block returns to its original internal order while staying in its new position, and the result is the rotation. Three passes of O(n) each and two index variables, versus the O(n) extra space of the copy-to-a-new-array approach.

04

Solution & live demo

python
1class Solution:
2 def rotate(self, nums, k):
3 n = len(nums)
4 k %= n
5 if k == 0:
6 return
7 
8 def rev(a, b):
9 while a < b:
10 nums[a], nums[b] = nums[b], nums[a]
11 a += 1
12 b -= 1
13 
14 rev(0, n - 1)
15 rev(0, k - 1)
16 rev(k, n - 1)
17 return
05

Edge cases

k = 0

Nothing changes — worth an early return.

k > n

The modulus reduces it; forgetting it causes an out-of-bounds slice.

k equal to n

The modulus makes it 0, so the array is unchanged.

Single element

Any rotation is a no-op.

06

Complexity

Time
O(n)
Space
O(1)
Three reversals in place. The copy-based version costs O(n) extra space.