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.

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.

Invariant: after each reverse, the relative order inside the reversed segment is fixed for the final result.

Algorithm (step-by-step)

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

Correctness sketch

• Invariant: after each reverse, the relative order inside the reversed segment is fixed for the final result.
• Reversing segments rearranges indices deterministically.
• The sequence of reversals maps each element to its rotated position.
• Thus the final array is exactly the desired rotation.

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.

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.