Problem
Given an integer array nums
, rotate the array to the right by k
steps, where k
is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 10<sup>5</sup>
-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
0 <= k <= 10<sup>5</sup>
Solution
Intuition
If I have [1,2,3,4,5,6,7] and k=3 then I need to shift 3 elements cyclically.
With that, my final result will be [5,6,7,1,2,3,4]
Initially, I was solving it by traditional approach like single shift, which took me O(kN) time.
To think differently, I have tried to understand the approach in a bottom-up approach: solution to the problem.
If I see [5,6,7] that is the k partition, [1,2,3,4] that is shifted element partition, if I reverse [1,2,3,4] I will get [4,3,2,1].
If I look whole combined array at this step, then it will be [7,6,5,4,3,2,1] which is, yes, you are right, the reversal of the original array.
So here I decode it like this:
Go from [1,2,3,4,5,6,7] to [7,6,5,4,3,2,1]: Reverse the whole array.
Now I need to reverse [7,6,5] which is the last k element of the array, it will seem as if we rotate them when this subpartition has been swapped. So we will have: [5,6,7,4,3,2,1]
Now look carefully you will observe [5,6,7] are at their place. You only make [4,3,2,1] right.
Again you are correct, reverse this sub-partition: [4,3,2,1] -> [1,2,3,4]
Voila, we have [5,6,7,1,2,3,4], our exact answer.
Approach
Reverse the whole array.
Reverse up to k.
Reverse from k+1 to the last index.
Complexity
Time complexity: O(N)
Space complexity: O(1)
Code
Java
class Solution {
public void reverse(int[] nums, int start, int end)
{
while(start<end)
{
nums[end] = nums[start]+nums[end]-(nums[start]=nums[end]);
start++;
end--;
}
}
public void rotate(int[] nums, int k) {
k=k%nums.length;
reverse(nums, 0, nums.length-1);
reverse(nums, 0, k-1);
reverse(nums, k, nums.length-1);
}
}
Python
class Solution:
def reverse(self, nums: List[int], start: int, end: int) -> None:
while start<end:
nums[start], nums[end] = nums[end], nums[start]
start+=1
end-=1
def rotate(self, nums: List[int], k: int) -> None:
k=k%len(nums)
self.reverse(nums, 0, len(nums)-1)
self.reverse(nums, 0, k-1)
self.reverse(nums, k, len(nums)-1)
I have also posted the same solution on Leetcode: https://leetcode.com/problems/rotate-array/solutions/4376260/fully-explained-readable-and-100-efficient-java-solution/