189. Rotate Array
Asked at Google, Meta, Microsoft, Walmart and 1 more
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Array
Companies
5
Problem
You are given an integer array nums and a non-negative integer k. Shift every element to the right by k positions, wrapping the elements that fall off the end back to the front. Modify nums directly — do not build and return a new array.
For example, rotating [1,2,3,4,5,6,7] right by 3 puts 5,6,7 at the front and pushes 1,2,3,4 to the back, giving [5,6,7,1,2,3,4]. The relative order inside each group stays the same.
A useful detail: rotating by k is the same as rotating by k % n, where n is the length of nums. If k is a multiple of n, the array does not change at all. The intended solution does the whole thing in place using only a constant amount of extra memory.
Right rotation by k = 3
Constraints
- ●
1 <= nums.length <= 10^5 - ●
-2^31 <= nums[i] <= 2^31 - 1 - ●
0 <= k <= 10^5
Examples
nums = [1,2,3,4,5,6,7], k = 3[5,6,7,1,2,3,4]nums = [-1,-100,3,99], k = 2[3,99,-1,-100]Asked At
5 companies| 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 → |
| TikTok | Medium | View all TikTok 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.
Three reverses, in place
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Rotate Array?
Rotate Array is asked at Google, Meta, Microsoft, Walmart, TikTok. 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.