Rotate Array

Rotate an integer slice to the right by k steps in-place. That is, each element moves to (i + k) % n.

The straightforward approach of shifting one step at a time is O(n*k) and too slow for large k. The goal is O(n) time and O(1) extra space.

Why this is worth learning

Rotation is a permutation of positions. Split the array into A followed by B, where B has k elements; the goal is BA without changing the order inside either block.

Before coding: one-minute experiment

Rotate [10,20,30,40,50] right by 7. What is k after normalization, and where does the original 10 go?

Function signature

func RotateArray(nums []int, k int)

Inputs / outputs

• nums: the slice to rotate in-place.
• k: number of steps to rotate right.
• Return: nothing; nums is modified in-place.

Example

nums = [1,2,3,4,5,6,7], k = 3
After rotation: [5,6,7,1,2,3,4]

Constraints

• 0 <= len(nums) <= 100_000
• 0 <= k <= 1_000_000_000

Core idea (near-solution)

Use the reverse trick:

1. Reverse the entire slice.
2. Reverse the first k elements.
3. Reverse the remaining n-k elements.

This works because reversing moves the last k elements to the front, and then the two additional reversals restore the order within each block.

State after each phase: the whole reversal produces reversed B followed by reversed A; the first-block reversal restores B; the final reversal restores A. Only a completed block has its final internal order.

Algorithm (step-by-step)

1. Let n = len(nums). If n == 0, return.
2. Reduce k with k %= n.
3. Reverse nums[:].
4. Reverse nums[:k].
5. Reverse nums[k:].

These are Go slices with exclusive upper bounds. If your helper instead accepts inclusive endpoint indices, the three calls use (0,n-1), (0,k-1), and (k,n-1); an empty segment does no swaps.

Correctness sketch

Handle n=0 before taking k modulo n. For nonempty input write the array as AB with |B|=k. Reversing the whole array produces reverse(B) followed by reverse(A). Reversing the first k positions restores B, and reversing the remainder restores A, yielding BA. Each reversal swaps symmetric positions and preserves all values. Reducing k modulo n is valid because n right rotations are the identity. Thus every original index i ends at (i+k) mod n.

Trace (hand walkthrough)

Example input:
nums = [1,2,3,4,5,6,7], k = 3
After rotation: [5,6,7,1,2,3,4]

Walk:
- k=3, reverse all: [7,6,5,4,3,2,1]
- reverse first k=3: [5,6,7,4,3,2,1]
- reverse rest: [5,6,7,1,2,3,4]

Pitfalls to avoid

• Forgetting k %= n (causes out-of-bounds or redundant work).
• Using extra slices (violates in-place requirement).
• Mixing up left and right rotation.

Debugging lens

Test k=0, k=n, k>n, and an empty input. A left rotation may preserve every value while still being the wrong permutation.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Implement a helper reverse(nums []int, l, r int) that swaps in-place.
• Check for n == 0 before k %= n to avoid division by zero.

Reconstruction checkpoint

Rotate [10,20,30,40,50] right by 7. What is k after normalization, and where does the original 10 go?

Return to Array & String · Module quiz