Rotate Array

Three reversals rotate in place

time O(n)space O(1)

Rotating right by k moves the last k values to the front and slides the rest back. The obvious fix is a copy, but that costs O(n) memory, and shifting one step at a time k times costs O(n*k). Reversing the whole array gets the tail to the front in one pass — it just leaves both halves backwards. Reversing each half separately straightens them out, so three linear reversals do the whole rotation in place.

Details

Animated on: nums = [1,2,3,4,5,6,7], k = 3 — rotate the array right by k steps, in place.

Problem:Rotate ArrayMedium

Three reversals rotate in place

step 1 / 11

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Rotating right by k=3 means the last 3 values [5, 6, 7] must end up at the front. Copying them aside would cost O(n) extra memory, so instead the whole row gets reversed and then un-reversed in two pieces.

Pseudocode

1FUNCTION rotate(nums, k):
2  n <- LENGTH(nums)
3  k <- k MOD n
4  REVERSE(nums, 0, n - 1)
5  REVERSE(nums, 0, k - 1)
6  REVERSE(nums, k, n - 1)
7  RETURN nums
8FUNCTION REVERSE(A, l, r):
9  WHILE l < r:
10    SWAP A[l] AND A[r]
11    l <- l + 1
12    r <- r - 1

← / → step · space play · Home restart

Every step in words

Show all 11 steps

Rotating right by k=3 means the last 3 values [5, 6, 7] must end up at the front. Copying them aside would cost O(n) extra memory, so instead the whole row gets reversed and then un-reversed in two pieces.
Reverse everything first: that drags the tail [5, 6, 7] to the front in one pass, which is the half of the job that actually matters.
Whole-array reverse: arr[0]=1 and arr[6]=7 were the outermost pair still out of order, so they trade and the row becomes [7, 2, 3, 4, 5, 6, 1].
Whole-array reverse: arr[1]=2 and arr[5]=6 were the outermost pair still out of order, so they trade and the row becomes [7, 6, 3, 4, 5, 2, 1].
Whole-array reverse: arr[2]=3 and arr[4]=5 were the outermost pair still out of order, so they trade and the row becomes [7, 6, 5, 4, 3, 2, 1].
The front 3 cells [7, 6, 5] are the right values but in backwards order, because the full reverse flipped them too. Reversing just this block puts them back.
Front block: arr[0]=7 and arr[2]=5 were the outermost pair still out of order, so they trade and the row becomes [5, 6, 7, 4, 3, 2, 1].
Same problem in the tail: [4, 3, 2, 1] holds the right values backwards, so reverse from index 3 to 6.
Back block: arr[3]=4 and arr[6]=1 were the outermost pair still out of order, so they trade and the row becomes [5, 6, 7, 1, 3, 2, 4].
Back block: arr[4]=3 and arr[5]=2 were the outermost pair still out of order, so they trade and the row becomes [5, 6, 7, 1, 2, 3, 4].
Both blocks are upright again, so the array is [5, 6, 7, 1, 2, 3, 4] — the original rotated right by 3, done with three reversals and no second array.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Rotate Array in the editor All Arrays problems Back to roadmap