AlgoScope

Rotate Array

Shift every value k places round. Reverse the whole thing, then each part, and it is done in place.

Array algorithms and techniques, algorithm, intermediate
The array is rotated right by 3.50617213243546
The array is rotated right by 3.50617213243546

Rotate, Partition, Select: Rotate right by 3

Result, step 11 of 11

Rotated by 3 in 6 swaps. Every value moved at most twice, so O(n) time and O(1) extra space.

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Before this

Variants

  • Reversal MethodThree in-place reversals.
  • Juggling / Cycle MethodFollow gcd(n, k) cycles.

Taught by the same lesson

Rotate, Partition, Select covers these too, in the same run.