Given an integer array nums and a non-negative integer k, rotate the array to the right by k steps, so each element moves k places to the right and elements falling off the end wrap around to the front. Modify nums in place.
Example 1
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
The last 3 elements
5,6,7 wrap around to the front.Example 2
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Constraints
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5
Hints
Frequently asked at: Microsoft, Amazon, Adobe, Zoho, Infosys
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Rotating one step at a time k times costs O(n * k). Copying into a new array at index (i + k) % n is O(n) but needs O(n) space. The reversal trick does it in place: after reversing the whole array, the last k elements are at the front but backwards, and the rest is also backwards. Reversing each of those two parts again fixes their order.
Algorithm
- Set
k = k % n(rotating by n changes nothing). - Reverse the whole array.
- Reverse the first
kelements. - Reverse the remaining
n - kelements.
Time:
O(n)Space: O(1)Interview tip: Forgetting
k % n is the classic bug: with k > n your reverse ranges go out of bounds. Also be ready to explain the cyclic replacement method as an alternative.class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k %= nΒ def reverse(i, j): while i < j: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1Β reverse(0, n - 1) # whole array reverse(0, k - 1) # first k reverse(k, n - 1) # the restCtrl + Enter runs the examples