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.

How to spot this pattern

Three reversals rotate in place with O(1) space. Reversing the whole array puts the tail at the front but backwards; reversing each of the two resulting segments straightens them out. The identity reverse(reverse(A) + reverse(B)) = B + A is the trick worth memorising.

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

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

Common pitfalls

Not reducing k modulo n

✗ Wrong
rev(0, k - 1)
✓ Right
k %= n

k may exceed the array length, and rotating by n is a no-op. Without the reduction the segment boundaries fall outside the array and the reversals corrupt or throw.

Reversing the segments in the wrong order

✗ Wrong
rev(0, n - k - 1)
rev(n - k, n - 1)
✓ Right
rev(0, k - 1)
rev(k, n - 1)

After the full reversal the last k elements now occupy the first k slots, so the split is at k, not n - k. Using the pre-reversal boundary rotates by the wrong amount.

Building a new array with slicing

✗ Wrong
nums[:] = nums[-k:] + nums[:-k]
✓ Right
rev(0, n - 1); rev(0, k - 1); rev(k, n - 1)

Correct and readable, but allocates O(n) extra space — the problem asks for an in-place O(1) solution. The three reversals touch each element at most twice with no allocation.

06

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.

07

Complexity

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