Rotate an array of n elements to the right by k steps
Given an array of size N and one value K. Your task is to perform a right rotation of the array K times and print rotated array.
arr = [1,2,3,4,5] , k=3
Output : [3,4,5,1,2]arr = [1,2,3,4,5] , k= 9
Output : [2,3,4,5,1]- N = arr.length
- 1 <= arr.length <= 10^5
- -2^31 <= arr[i] <= 2^31 - 1
- 0 <= k <= 10^5
Approach 1 : Brute Force
Brute-force approach involves performing K rotations of the array. For one rotation shifts all elements one position to the right, with the last element moving to the first position.
#include <bits/stdc++.h>
using namespace std;
void rotateArray(int arr[], int n,int k)
{
while(k>0) {
int last=arr[n-1];
for(int i=n-1; i>0; i--) {
arr[i]=arr[i-1];
}
arr[0]=last;
k--;
}
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
rotateArray(arr,n,k);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}3 4 5 1 2
Time Complexity
We are iterating over array k times so Time Complexity will be => O(kN)
Space Complexity
Since we are not using any extra storage so Space Complexity will be => O(1).
For every N rotation the array will become the same as the initial array so array rotation of k will be same as array rotation of k%N so fist optimization we can perform on any approach is k = k%N.
Approach 2 : Printing Rotated Array Without Changing Array
- First take the mod k= k%N
- First print last k element from index N-k to N-1
- print starting n-k element from index 0 to n-k-1
#include <bits/stdc++.h>
using namespace std;
void rotateArray(int arr[], int n,int k)
{
k=k%n;
for(int i=n-k; i<n; i++) {
cout << arr[i] << " ";
}
for (int i = 0; i < n-k; i++) {
cout << arr[i] << " ";
}
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 9;
rotateArray(arr,n,k);
}2 3 4 5 1
Time Complexity
We are iterating array once so Time Complexity will be => O(N).
Space Complexity
Since we are not using any extra storage so space complexity will be => O(1).
Approach 3 : Reversing the array
Idea behind this approach is to reverse the array three times.
Steps :
- Reverse the entire array.
- Reverse the first k elements.
- Reverse the remaining last n−k elements.
#include <bits/stdc++.h>
using namespace std;
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void reverse(int arr[], int start, int end)
{
while (start < end) {
swap(arr, start, end);
start++;
end--;
}
}
void rotateArray(int arr[], int n,int k)
{
k=k%n;
reverse(arr,0,n-1);
reverse(arr,0,k-1);
reverse(arr,k,n-1);
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 12;
rotateArray(arr,n,k);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}4 5 1 2 3
Time Complexity
we are reversing array so Time Complexity will be => O(N).
Space Complexity
Since we are not using any extra storage so Space Complexity will be => O(1).
OR
- Reverse last k element.
- Reverse first n-k element
- Reverse the entire array.
#include <bits/stdc++.h>
using namespace std;
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void reverse(int arr[], int start, int end)
{
while (start < end) {
swap(arr, start, end);
start++;
end--;
}
}
void rotateArray(int arr[], int n,int k)
{
k=k%n;
// reverse last k element
reverse(arr,n-k,n-1);
// reverse first n-k element
reverse(arr,0,n-k-1);
// reverse array
reverse(arr,0,n-1);
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 12;
rotateArray(arr,n,k);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}4 5 1 2 3
Time Complexity
we are reversing array so Time Complexity will be =>O(N).
Space Complexity
Since we are not using any extra storage so Space Complexity will be => O(1).