Rotate Array Elements by ‘D’ Positions

Rotate Array Elements by ‘D’ Positions” is one of the most favorite technical interview problem based on array data structure. Here, we are given an array with ‘n’ elements and a ‘d’ value. Our task is to rotate the given array by ‘d’ positions in clock wise manner.

Example:

Given Array
Arr[] = {34, 67 11, 23, 78, 89}
Rotating Array by 2 places
Arr[] = {11, 23, 78, 89, 34, 67}

There are multiple methods to rotate the array by ‘D’ positions. Some of them are:

METHOD 1: Brute-Force

The simplest solution to rotate the given array by ‘D’ positions is to run two nested loops. Rotate the position of each element of array by ‘D’ times. The time complexity of this solution is O(n^2), where ‘n’ is the size of the array.

C++ Program to Rotate Array by ‘D’ position is as follows:

#include<bits/stdc++.h>
using namespace std;
void printArray(int arr[],int n)
{
    for(int i = 0 ; i < n ; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
void rotateArray(int arr[],int n,int D)
{
    // Rotate 'D' times
    for(int  k = 1 ; k <= D ; k++)
    {    
        //store the first element in temporary variable
        int temp = arr[0];
        // Shifting Elements by one Elements
        for(int i = 1 ; i < n ; i++)
        {
            arr[i-1] = arr[i];
        }
        // Assign the temporary variable to last index
        arr[n-1] = temp;
    }
}

int main()
{
    int arr[5] = {78, 89, 34, 11, 23};
    cout<<"Array Before Rotating:\n";
    printArray(arr,5);
    cout<<"Rotate the array by two places!!";
    rotateArray(arr,5,2);
    cout<<"\nArray After Rotating:\n";
    printArray(arr,5);
}

OUTPUT:
Array Before Rotating:
78 89 34 11 23 
Rotate the array by two places!!
Array After Rotating:
34 11 23 78 89

METHOD 2: Efficient with Extra Space

The steps required to rotate an array by ‘D’ position are as follows:

  1.  The efficient method would to create a temporary array of same size ‘n’.
  2. Now, copy array elements from position ‘d’ to ‘n-1’ into temporary array from position ‘0’ to ‘n-d’.
  3. Now, copy the  array elements from position ‘0’ to ‘d-1’ into temporary array from position ‘n-d+1’ to ‘n-1’.
  4. Now, copy all the elements of temporary array to original array.

The time complexity of this solution is O(n), where ‘n’ is the size of array. 

C++ Program to rotate an Array by ‘d’ Elements is as follows:

#include<bits/stdc++.h>
using namespace std;
void printArray(int arr[],int n)
{
    for(int i = 0 ; i < n ; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
void rotateArray(int arr[],int n,int D)
{
    int temp[n];
    int index = 0;
    // Copy the Elements from index 'D' to 'n-1'
    for(int  i = D ; i < n ; i++)
    {
        temp[index] = arr[i];
        index++;
    }
    // Copy the Elements from '0' to 'D-1'
    for(int i = 0 ; i < D ; i++)
    {
        temp[index] = arr[i];
        index++;
    }
    // Copy back the Elements back to 
    for(int i = 0 ; i < n ; i++)
    {
        arr[i] = temp[i];
    }
}
int main()
{
    int arr[5] = {78, 89, 34, 11, 23};
    cout<<"Array Before Rotating:\n";
    printArray(arr,5);
    cout<<"Rotating Array by two positions!!";
    rotateArray(arr,5,2);
     cout<<"\nArray After Rotating:\n";
    printArray(arr,5);
}
OUTPUT:
Array Before Rotating:
78 89 34 11 23 
Rotate the array by two places!!
Array After Rotating:
34 11 23 78 89

METHOD 3: In-place Reversal

This is little tricky solution, but solves the problem in O(n) time complexity and without extra space.

The steps required to rotate an array by ‘D’ Elements are as follows:

  1. Reverse the array from position 0 to ‘D-1’.
  2. Reverse an array from position ‘D’ to ‘n-1’.
  3. Reverse whole Array.

C++ Program to rotate an array by ‘d’ positions is as follows:

#include<bits/stdc++.h>
using namespace std;
void printArray(int arr[],int n)
{
    for(int i = 0 ; i < n ; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
void reverseArray(int arr[],int start,int end)
{
    for(int i = start, j = end ; j>i; i++,j--)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
void rotateArray(int arr[],int n,int D)
{
    // Reverse an array from '0' to 'D-1'
    reverseArray(arr,0,D-1);
    // Reverse an array from 'D' to 'n-1'
    reverseArray(arr,D,n-1);
    // Reverse a whole Array
    reverseArray(arr,0,n-1);
}
int main()
{
    int arr[5] = {23, 44, 67, 89, 45};
    cout<<"Array Before Rotating:\n";
    printArray(arr,5);
    cout<<"Rotating Array by 2 positions!!";
    rotateArray(arr,5,2);
    cout<<"\nArray After Rotating:\n";
    printArray(arr,5);
}
OUTPUT:
Array Before Rotating:
23 44 67 89 45 
Rotating Array by 2 positions!!
Array After Rotating:
67 89 45 23 44

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *