Array Rotation

Array rotation is a problem of changing the order of the elements of the array. Decreasing the index of the element by one and changing the index of the first element to n-1 (n is the size of the array) and so on.

Problem

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 splitted from array A[], such that A[0..n-1] = P[0..p-1] Q[p..n-1]

- 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);
    
}

int main() {
    int A[N] = {5, 2, 4, 6, 1};
    int d = 4;
    
    Rotate(A, d);
    
    cout<<"Array after "<<d<<" rotations:"<<endl;
    printArray(A);
    
    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 the problem states rotate the array by d to the right, set d = n-d, and rotate to the left.