189. Rotate Array
mediumRotate an array right by k steps, in-place, with O(1) extra space. The elegant solve uses three reversals — a trick that surprises candidates the first time they see it.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Constraints
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 10 <= k <= 10^5
Examples
Example 1
nums = [1,2,3,4,5,6,7], k = 3[5,6,7,1,2,3,4]Explanation: rotate 1 step right: [7,1,2,3,4,5,6]; rotate 2: [6,7,1,2,3,4,5]; rotate 3: [5,6,7,1,2,3,4].
Example 2
nums = [-1,-100,3,99], k = 2[3,99,-1,-100]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Allocate a copy: easy, but uses O(n) extra space.
Hint 2
k can be larger than n. Always start with k = k % n.
Hint 3
Reverse the entire array, then reverse the first k elements, then reverse the remaining n-k elements. That's three O(n) passes and O(1) extra space.
Solution approach
Reveal approach
Normalize k = k % n (since rotating by n is a no-op). Then perform three in-place reversals: reverse the whole array, reverse nums[0..k-1], and reverse nums[k..n-1]. The combined effect is a right-rotation by k. O(n) time and O(1) extra space. Alternative approaches include using an extra array (O(n) space) or cyclic replacements with a position-tracking algorithm (correct but trickier to implement cleanly).
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- array-manipulation
Related problems
- 344. Reverse String
- 48. Rotate Image
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Meta
Practice these live with InterviewChamp.AI
Drill Rotate Array and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →