Problem:
Given an integer array and a number k , rotate the array by k positions to the right.
For example,
If the given array is
[1,2,3,4,5,6,7,8]
and k = 4
Then the output is
[5,6,7,8,1,2,3,4]
Pushing an element out of the array makes it land in the beginning of the array.
Try out the solution here:
https://leetcode.com/problems/rotate-array/
Solution:
Approach 1 – Use additional memory
The solution is fairly straightforward using additional memory.
Create an array of the same size as the input.
Copy the last k elements in the first k positions in the result array.
Then copy the first n – k elements (n is the size of the array) into the remaining positions.
Once the result array is ready copy back the elements to the original array.
Here is the code:
class Solution {
public void rotate(int[] nums, int k) {
if(k > nums.length) k = k % nums.length ;
int[] result = new int[nums.length];
int index=0;
int start = nums.length - k;
for(int i=start;i<nums.length;i++){
result[index++] = nums[i];
}
for(int i=0;i<start;i++){
result[index++] = nums[i];
}
for(int i=0;i<result.length;i++){
nums[i] = result[i];
}
}
}
Notice that rotating an array of size n , n times places the elements in the same position as before.
So if k is greater than n , then we should find the modulus of k % n and perform that many number of rotations.
The time complexity in this approach is O(n) .
And space complexity is also O(n).
Approach 2 – Using k additional memory
Instead of using O(n) space complexity we can use constant space O(1).
In this approach we create an additional array of size k.
We will copy all the last k elements of the input array to this array.
Then we will move the remaining elements of the array to the end , making space for the k elements.
After this we copy the elements from the k array to the first k positions.
By doing this our space complexity is reduced.
Time complexity remains the same.
here is the code:
class Solution {
public void rotate(int[] nums, int k) {
if(k > nums.length ) k = k % nums.length;
int[] karray = new int[k];
int index = 0;
for(int i= nums.length - k ;i<nums.length;i++){
karray[index++] = nums[i];
}
int last = nums.length - k - 1;
int end = nums.length - 1;
while(last >=0){
nums[end] = nums[last];
end--;
last--;
}
for(int i=0;i<k;i++){
nums[i] = karray[i];
}
}
}
Approach 3 – In place rotation
In this approach , we are going to get rid of the k array as well.
There is no additional memory required.
Below is the algorithm:
- Reverse the entire array
- Reverse the first k elements of the reversed array
- Reverse the last n – k elements of the reversed array.
That gives us the required output.
Here is the code:
class Solution {
int[] nums;
public void rotate(int[] nums, int k) {
this.nums = nums;
if(k > nums.length) k = k % nums.length ;
reverse(0,nums.length-1);
reverse(0,k-1);
reverse(k,nums.length-1);
}
public void reverse(int first,int last){
while(first < last){
int t = nums[first];
nums[first] = nums[last];
nums[last] = t;
first++;
last--;
}
}
}
Time complexity is O(n) and space complexity is O(1)
That’s it!
Leave a Reply