189. Rotate Array

Quick Identifier

• Topic: arrays-hashing
• Pattern: The Triple Reverse Trick
• Hint: Don't try to shift elements one by one, and don't try to map indices in an $O(1)$ cyclic replacement (it's too hard to code without bugs). Instead, just reverse the whole array, then reverse the two halves independently.
• Difficulty: Medium
• Companies: Amazon, Microsoft, Apple, Google, Meta
• LeetCode: 189

Quick Sights

• Time Complexity: O(n). Reversing the entire array takes $O(n)$. Reversing the two halves takes another $O(n)$. Total time is $O(2n)$, which simplifies to $O(n)$.
• Space Complexity: O(1). The problem explicitly asks for an in-place modification.
• Core Mechanism:
  1. Normalize k (because rotating an array of length 5 by 6 steps is the same as rotating by 1 step). k = k % n.
  2. Reverse the entire array from 0 to n - 1.
  3. Reverse the first k elements (from 0 to k - 1).
  4. Reverse the remaining n - k elements (from k to n - 1).

Concept Explanation

As a senior engineer, the "Triple Reverse" trick is a piece of algorithmic trivia that you simply must know. Trying to derive it from first principles during an interview is unnecessary.

1. The Brute Force Danger: If you try to literally "pop" an element off the back and "unshift" it to the front k times, you are doing an $O(n)$ operation $k$ times. This is $O(n \cdot k)$ and will time out.
2. The Cyclic Replacement Nightmare: The mathematical alternative is to jump indices: temp = nums[i], nums[(i+k)%n] = temp. But what happens if k and n share a greatest common denominator? You end up in infinite loops and have to track visited elements. It is an absolute nightmare to write bug-free on a whiteboard.
3. The Elegant Geometric Solution: Look at an array as two blocks: Block A (the part that will stay in the front but shift right) and Block B (the part that will wrap around to the very front).
   • Original: [ Block A | Block B ]
   • Goal: [ Block B | Block A ]
   • Reverse the whole thing: [ Reversed B | Reversed A ]
   • Reverse the chunks independently: [ Block B | Block A ]. Magic.

Diagram

This flowchart outlines the three distinct reversal phases.

Study Pattern (SDE3+)

• 0–3 min: Immediately name the "Triple Reverse" method. Explain why Cyclic Replacement is dangerous to code under pressure, and why $O(n \cdot k)$ element-shifting is a failure.
• Implementation pass: Write a modular reverse(nums, start, end) helper function. Do not write the while (start < end) logic three separate times in your main function. It looks amateurish.
• 5 min extension: What if the interviewer asks you to rotate the array left instead of right? The algorithm is identical, but the boundaries change. For a left rotation of k, you reverse 0 to k-1, then k to n-1, and then reverse the whole array. (Alternatively, rotating left by k is identical to rotating right by n - k).

Approaches

• Shift One-by-One — Move the last element to the front, k times. Time: $O(n \cdot k)$, Space: $O(1)$. TLE (Time Limit Exceeded).
• Extra Array / Slice — Cut the array into two pieces and paste them together into a new array. Time: $O(n)$, Space: $O(n)$. Fails the $O(1)$ space constraint.
• Triple Reverse — Time: $O(n)$, Space: $O(1)$. (Always pick this)

Optimal Solution

Go

func rotate(nums []int, k int) {
	n := len(nums)
	if n == 0 {
		return
	}

	// Normalize k to prevent unnecessary rotations
	k = k % n

	// Phase 1: Reverse the entire array
	reverse(nums, 0, n-1)

	// Phase 2: Reverse the first k elements
	reverse(nums, 0, k-1)

	// Phase 3: Reverse the remaining n - k elements
	reverse(nums, k, n-1)
}

// Helper function to reverse a segment of the array in-place
func reverse(nums []int, start int, end int) {
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
}

JavaScript

function rotate(nums, k) {
	const n = nums.length;
	if (n === 0) return;

	// Normalize k
	k = k % n;

	// Apply the triple reverse
	reverse(nums, 0, n - 1);
	reverse(nums, 0, k - 1);
	reverse(nums, k, n - 1);
}

function reverse(nums, start, end) {
	while (start < end) {
		// Swap elements
		const temp = nums[start];
		nums[start] = nums[end];
		nums[end] = temp;

		start++;
		end--;
	}
}

Walkthrough

Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3 Length n = 7. k % n = 3.

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

Edge Cases

• k is exactly a multiple of n (e.g., n = 5, k = 10). k % n becomes 0. The first reverse flips it, the second reverse is a no-op, the third reverse flips it back to the original. Correct behavior, but slightly wasteful. (You can add an if (k == 0) return to optimize).
• k is larger than n. Handled cleanly by k % n.
• Array length is 1. All reverses instantly terminate because start < end is false.

Pitfalls

• Forgetting to modulo k. If k = 5 and n = 3, passing k-1 (4) to the reverse function will cause an index out of bounds error.
• Passing k instead of k-1 as the end index for Phase 2. Remember, arrays are 0-indexed. The kth element is at index k-1.

Similar Problems

• 048. Rotate Image — Similar conceptual composition of operations (Transpose + Reverse) to achieve rotation.
• 151. Reverse Words in a String — Another string/array problem heavily utilizing the "reverse parts, then reverse whole" trick.

Mind-Map Tags

#arrays #in-place #reverse #rotation #modular-math