Rotate Array
Asked at Google, Meta, Microsoft, Walmart
Problem
Given an integer array nums and an integer k, rotate the array to the right by k steps. For example, [1,2,3,4,5,6,7] rotated by 3 becomes [5,6,7,1,2,3,4]. This problem tests your ability to think about in-place array transformations using the three reverses technique.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: rotate one step at a time, k times. Each rotation moves every element one position to the right. That's O(n * k) -- too slow for large k.
Better approach: use an extra array. Calculate where each element goes: (i + k) % n gives the new position. Copy to the new array, then copy back. That's O(n) time but O(n) space.
Key insight: the three reverses technique. To rotate right by k: (1) reverse the entire array, (2) reverse the first k elements, (3) reverse the remaining n-k elements. This transforms the array in-place with O(1) space.
Why three reverses work: consider [1,2,3,4,5,6,7] with k=3.
Original: [1,2,3,4,5,6,7]
Step 1 - Reverse all: [7,6,5,4,3,2,1]
Step 2 - Reverse first k=3: [5,6,7,4,3,2,1]
Step 3 - Reverse remaining n-k=4: [5,6,7,1,2,3,4]
Result: [5,6,7,1,2,3,4] -- correct!
The reverse operation moves the last k elements to the front while preserving their relative order.
Edge cases: k > n (use k = k % n). k = 0 (no rotation). k = n (full rotation, array unchanged). Single element array. Two element array.
Optimal Approach
Step 1: Handle edge case: k = k % n (in case k > n).
Step 2: Reverse the entire array.
Step 3: Reverse the first k elements (indices 0 to k-1).
Step 4: Reverse the remaining n-k elements (indices k to n-1).
Walkthrough for nums = [1,2,3,4,5,6,7], k = 3:
- k = 3 % 7 = 3
- Reverse all: [7,6,5,4,3,2,1]
- Reverse [0:3]: [5,6,7,4,3,2,1]
- Reverse [3:7]: [5,6,7,1,2,3,4]
- Result: [5,6,7,1,2,3,4]
Walkthrough for nums = [-1,-100,3,99], k = 2:
- k = 2 % 4 = 2
- Reverse all: [99,3,-100,-1]
- Reverse [0:2]: [3,99,-100,-1]
- Reverse [2:4]: [3,99,-1,-100]
- Result: [3,99,-1,-100]
Time: O(n) -- three passes through the array. Space: O(1) -- only a temp variable for swapping.
What Trips People Up in Real Interviews
Forgetting k = k % n. When k > n, the rotation wraps around. Without the modulo, you might reverse beyond array bounds or get incorrect results. Always normalize k first.
Reversing the wrong segments. The three reverses are: (1) entire array, (2) first k elements, (3) remaining n-k elements. Reversing in a different order or with different boundaries gives wrong results.
Using an extra array for the rotation. While O(n) space works, interviewers expect the O(1) in-place three reverses solution. The extra array approach shows you don't know the optimal technique.
Confusing left rotation with right rotation. The three reverses technique described is for RIGHT rotation. For LEFT rotation by k, reverse the first k elements, then the remaining n-k, then the entire array.
Not handling k=0 or k=n. When k=0, no rotation is needed. When k=n, the array returns to its original state. Both should work correctly with the modulo and reversal approach.
Solution Code
def rotate(nums, k):
n = len(nums)
k = k % n
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)Frequently Asked Questions
What is the Rotate Array problem?
Given an integer array nums and an integer k, rotate the array to the right by k steps. For example, [1,2,3,4,5,6,7] rotated by 3 becomes [5,6,7,1,2,3,4]. This problem tests your ability to think about in-place array transformations using the `three reverses` technique.
How do you solve Rotate Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Rotate Array?
Rotate Array is asked at Google, Meta, Microsoft, Walmart. It is a medium difficulty problem.
What are common mistakes on Rotate Array?
- Forgetting `k = k % n`. When k > n, the rotation wraps around. Without the modulo, you might reverse beyond array bounds or get incorrect results. Always normalize k first.
- Reversing the wrong segments. The three reverses are: (1) entire array, (2) first k elements, (3) remaining n-k elements. Reversing in a different order or with different boundaries gives wrong results.
- Using an extra array for the rotation. While `O(n)` space works, interviewers expect the `O(1)` in-place `three reverses` solution. The extra array approach shows you don't know the optimal technique.
- Confusing left rotation with right rotation. The `three reverses` technique described is for RIGHT rotation. For LEFT rotation by k, reverse the first k elements, then the remaining n-k, then the entire array.
- Not handling k=0 or k=n. When k=0, no rotation is needed. When k=n, the array returns to its original state. Both should work correctly with the modulo and reversal approach.