Rotate Array by K Steps

Problem Statement

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Do it in-place with O(1) extra space if possible.

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

Example

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

Output: [5,6,7,1,2,3,4]

Explanation: Rotate right 3 times.

What the Interviewer Expects

1. Handle k > length — use k = k % n first.
2. Naive approaches — extra array (O(n) space) or rotating one step k times (O(n·k) time). Acknowledge these.
3. Optimal: reversal trick — O(n) time, O(1) space:
   • Reverse the entire array
   • Reverse the first k elements
   • Reverse the remaining n-k elements
4. Dry run the reversal approach to prove correctness.

Follow-ups

1. What if you had to rotate left instead of right?
2. Can you do it using the cyclic replacement (juggling) algorithm? What's the complexity?
3. What if the array is a linked list instead?
4. What if k can be negative (rotate left)?