Rotate Array

Medium#189towards each other

You get an array of numbers and a number k. Shift the array k places to the right in a circle: the numbers that fall off the end come back at the start. Do it inside the same array, without a second one. Our example: [1, 2, 3, 4, 5, 6], k = 2 → [5, 6, 1, 2, 3, 4].

189 Rotate ArrayWalkthrough · 1×

Example: [1, 2, 3, 4, 5, 6], k = 2. Three reverses: the whole array, then the first k, then the rest. In each one left and right walk in from the ends of its range and swap.

Shift right by k = 2011223344556
in this reverse, not swapped yetunder a pointerjust swappedalready swappedoutside this reverse

n = 6: the array has 6 numbers

01/30
restart · back · play · step
Speed
1function rotate(nums, k):
2 n = len(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
8
9function reverse(nums, left, right):
10 while left < right:
11 swap nums[left] and nums[right]
12 left = left + 1; right = right - 1
state
n
6
k
–
left
–
right
–
nums
[1, 2, 3, 4, 5, 6]
click a step to go back

← → step · space play/pause

Why it works

  1. After the shift the last k numbers stand at the front, and the rest follow them. Reversing the whole array already puts each group in its place, only each group is backwards.
  2. Reversing each group on its own turns it the right way round again, so the order inside each group is the old one.
  3. A shift by n brings the array back to where it was, so a k of n or more shifts the same as k mod n. Take k = k mod n first, or the reverse of the first k runs past the end.

Complexity

Time O(n): the three reverses swap each number at most twice. Memory O(1): the numbers trade places inside the same array, with no second one.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.