Rotate Array LeetCode 189 Deep Dive

LeetCode 189 Rotate Array asks you to rotate an integer array to the right by k steps. The rotation must be performed in-place, modifying the input array directly. For example, rotating [1,2,3,4,5,6,7] by k=3 gives [5,6,7,1,2,3,4] — the last three elements wrap around to the front.

The problem includes a follow-up challenge: can you solve it with O(1) extra space? This rules out the naive approach of copying to a new array, pushing you toward smarter in-place strategies. Understanding the O(1) solution is what interviewers are actually testing.

Key edge cases include k larger than n (since rotating by n is a no-op, compute k = k % n first) and k equal to 0 (no rotation needed). The constraints allow up to 10^5 elements and k up to 10^5.

The simplest approach uses an auxiliary array of the same length. For each element at index i in the original array, place it at position (i + k) % n in the new array. After filling the new array, copy it back into the original. This is O(n) time and O(n) space.

The formula newArr[(i + k) % n] = nums[i] works because adding k to every index and wrapping around with modulo exactly describes a rotation. It is easy to reason about and implement correctly on the first try, making it a safe fallback if you blank on the in-place trick during an interview.

The downside is the O(n) space requirement. Allocating a new array of the same size fails the follow-up constraint. For arrays with millions of elements, the extra allocation can be costly in practice. This is why interviewers specifically ask for the O(1) approach.

The triple reversal method rotates the array in-place using exactly three reverse operations — no extra memory beyond a temporary swap variable. Each reversal is O(n/2) swaps, giving O(n) total time and O(1) space.

The three steps operate on different slices of the array. Step 1 reverses the entire array. Step 2 reverses only the first k elements. Step 3 reverses the remaining n-k elements. After all three steps the array is rotated right by k positions.

Remember to compute k = k % n before starting. If k is 0 after the modulo, return immediately — no work needed. A helper reverse(nums, left, right) function that swaps elements inward from both ends makes the three steps clean and readable.

To understand the triple reversal, consider [1,2,3,4,5,6,7] with k=3. Reversing all gives [7,6,5,4,3,2,1]. The last k=3 elements (5,6,7) are now at the front but in reversed order. The first n-k=4 elements (1,2,3,4) are now at the back but also reversed.

Reversing the first k elements [7,6,5] gives [5,6,7] — restoring their original relative order at the front. Reversing the remaining [4,3,2,1] gives [1,2,3,4] — restoring their order at the back. The combined result [5,6,7,1,2,3,4] is exactly the rotation we wanted.

The intuition: reversing all elements interleaves the two halves (the last-k block and the first n-k block) in reversed order. The two subsequent reversals undo the individual reversals within each half, leaving only the cyclic shift. Two negatives make a positive — reversed twice means back to original relative order, but in the correct rotated position.

Cyclic replacement places each element directly at its target position (i + k) % n, displacing whatever was there, then placing the displaced element at its own target, and continuing the chain. This achieves O(n) time and O(1) space without the reversal trick.

The algorithm starts at index 0, saves the current value, writes the saved value to its target, saves the overwritten value, and repeats. When the chain returns to the starting index (cycle closes), move to the next unvisited starting index. Track count — when count equals n, all elements have been placed and you are done.

Cyclic replacement is harder to implement correctly than triple reversal. You must handle the case where gcd(n, k) > 1, which creates multiple independent cycles. The count variable is the standard fix: keep looping until count == n regardless of how many cycles there are. Most interviewers prefer the triple reversal for its clarity.

Python triple reversal: define a helper reverse(nums, l, r) that swaps inward while l < r. In rotate(nums, k): compute k = k % len(nums); if k == 0 return. Call reverse(nums, 0, n-1), then reverse(nums, 0, k-1), then reverse(nums, k, n-1). The mutation is in-place — Python lists are mutable and passed by reference. Time O(n), space O(1).

Java triple reversal: same three-step pattern. The helper private void reverse(int[] nums, int l, int r) swaps using a temp variable. In rotate: n = nums.length; k %= n; if k == 0 return. Call reverse(nums, 0, n-1); reverse(nums, 0, k-1); reverse(nums, k, n-1). Java arrays are also passed by reference so the in-place mutation works identically.

Both solutions pass all LeetCode 189 test cases. The Python solution is typically 4-6 lines for the helper and 4 lines for rotate — concise enough to write quickly under interview pressure. The Java version is slightly more verbose but identical in structure. Memorize the three reverse calls and the k %= n guard.

Rotate Image (LeetCode 48) applies a 2D version of the same rotation intuition: transpose the matrix then reverse each row (or reverse each row then transpose for counter-clockwise rotation). The triple reversal trick for 1D arrays has a direct analogue in the two-step matrix rotation.

Spiral Matrix (LeetCode 54) and Move Zeroes (LeetCode 283) belong to the in-place array manipulation family. Move Zeroes uses a two-pointer technique to shift non-zero elements forward — the same O(n) time O(1) space constraint applies. Understanding in-place array manipulation is a transferable skill across many LeetCode problems.

The broader rotation family includes Best Rotation with K Increments (LeetCode 798), which optimizes rotation score, and Find Minimum in Rotated Sorted Array (LeetCode 153), which binary searches a rotated array. Recognizing a rotated array structure — where elements wrap around — is a key pattern for medium and hard array problems.