Array Rotation

Array rotation is a problem of changing the order of the elements of the array. Increasing the index of the element by one and changing the index of the last element to 0 and so on.

Problem Statement: Given an array arr[] of size n, rotate it by d elements. 

Example : 

Input :  arr[] = [1, 2, 3, 4, 5, 6, 7]
         d = 2
Output : arr[] = [3, 4, 5, 6, 7, 1, 2] 

Naive Approach

Let rotate the array arr[] by one element at a time, and do this operation d times.

Pseudocode

RotateByOneElement (A[])
1.  temp = A[0]
2.  for i=0 to n-2
3.    A[i] = A[i+1]
4.  A[n-1] = temp

Rotate (A[], d)
1. for i=0 to d
2.   RotateByOneElement (A)

Code Implementation

//
//  main.cpp
//  Array Rotation
//
//  Created by Himanshu on 18/09/21.
//

#include <iostream>

using namespace std;
const int N = 5;

void printArray (int A[]) {
    for (int i=0; i<N; i++) {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}

void RotateByOneElement (int A[]) {
    int temp = A[0];
    
    for (int i=0; i<N-1; i++) {
        A[i] = A[i+1];
    }
    A[N-1] = temp;
}

void Rotate (int A[], int d) {
    cout<<"Array:"<<endl;
    printArray(A);
    for (int i=1; i<=d; i++) {
        RotateByOneElement(A);
        cout<<"Array after "<<i<<" rotation:"<<endl;
        printArray(A);
    }
}

int main() {
    int A[N] = {5, 2, 4, 6, 1};
    int d = 4;
    Rotate(A, d);
    
    return 0;
}

Output

Array:
5 2 4 6 1 
Array after 1 rotation:
2 4 6 1 5 
Array after 2 rotation:
4 6 1 5 2 
Array after 3 rotation:
6 1 5 2 4 
Array after 4 rotation:
1 5 2 4 6 

Time complexity : O(N*d) 
Auxiliary Space : O(1)

Here’s a working example: Array Rotation

Reversal Algorithm

Reversal algorithm is an algorithm for rotating an array. In this algorithm, subarrays are created and reversed to perform the rotation of the array. Subarrays are rotated individually and then joined together and reversed back to get the rotated array.

Pseudocode
Rotate (A[], d)
  //Split the array into two subarrays A[0, d-1] & A[d, n-1]
  reverse(arr[], 0, d-1) ;
  reverse(arr[], d, n-1);
  //Reverse the entire array
  reverse(arr[], 0, n-1);
Proof

Let P and Q be the two subarrays splited from array A[]

  • Reverse P to get P’Q, where P’ is reverse of P.
  • Reverse Q to get P’Q’, where Q’ is reverse of Q.
  • Reverse all to get (P’Q’) ‘ = QP.
  • Hence Array A[] is rotated to the left by size[P].

Code Implementation

//
//  main.cpp
//  Reversal Algorithm (Array rotation)
//
//  Created by Himanshu on 18/09/21.
//

#include <iostream>

using namespace std;
const int N = 5;

void printArray (int A[]) {
    for (int i=0; i<N; i++) {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}

void Reverse (int A[], int p, int q) {
    int temp;
    for(int i=p, j=q; i<j; i++, j--) {
        temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

void Rotate (int A[], int d) {
    cout<<"Array:"<<endl;
    printArray(A);
    
    Reverse(A, 0, d-1);
    Reverse(A, d, N-1);
    Reverse(A, 0, N-1);
    
    cout<<"Array after "<<d<<" rotations:"<<endl;
    printArray(A);
    
    
}

int main() {
    int A[N] = {5, 2, 4, 6, 1};
    int d = 4;
    Rotate(A, d);
    
    return 0;
}

Output

Array:
5 2 4 6 1 
Array after 4 rotations:
1 5 2 4 6 

Time complexity : O(N) 
Auxiliary Space : O(1)

Here’s a working example: Array Rotation (Reversal Algorithm)

Quick tip:
If problem states, rotate the array by d to the right, set d = n-d and rotate to the left.


Leave a Reply