Rotate Array
The key idea
Rotating right by
k means the last k elements move to the front. Reverse the whole array, then reverse the first k and the remaining n - k separately. The two local reversals undo the order-scrambling of the global reverse while keeping the two blocks swapped, giving the rotation in O(1) space. Remember to take k % n so a k larger than the length still works.Problem
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Each rotation by one step moves every element one position to the right, and the last element wraps around to the front. After k such steps, the last k elements end up at the front of the array, in their original relative order.
Try to solve it in-place with O(1) extra space.
Constraints
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 10 <= k <= 10^5
Examples
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Two Pointers problems
- 3SumMEDIUM
- 4SumMEDIUM
- Concatenation of ArrayEASY
- Container With Most WaterMEDIUM
- Is SubsequenceEASY
- Merge Sorted ArrayEASY
- Merge Strings AlternatelyEASY
- Move ZeroesEASY
- Next PermutationMEDIUM
- Remove Duplicates from Sorted ArrayEASY
- Remove Duplicates from Sorted Array IIMEDIUM
- Remove ElementEASY