Rotate an array of 𝑛 elements to the right by 𝑘 steps

DevSniper
Published : 20 July 2024

202 Views

Array Data Structures Array List Coding Problems DSA

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.

Example 1 :-

arr = [1,2,3,4,5] , k=3

Output : [3,4,5,1,2]

Example 2 :-

arr = [1,2,3,4,5] , k= 9

Output : [2,3,4,5,1]

Constraints :

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.

C++

Java

#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

C++

Java

#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.

C++

Java

#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.

C++

Java

#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).