Reversal Algorithm for Array Rotation

Rubleen Kaur Hanspal
Last Updated: May 13, 2022

Introduction

The problem we are going to discuss is to rotate a given array and we are given the array and its rotating index. Array rotation means observing the elements in a circular manner and shifting each element of the array according to the direction of the rotation, which is given in the problem. 
 

Let’s say we are given a simple array of 5 numbers, arr[] =[1,2,3,4,5], and we are told to perform a right-side array rotation by 1.
 


The above diagram is a small representation of how right array rotation works.

 

We have discussed Array Rotation and its different approaches in a blog. To understand the concept better, do give it a read.

 

This blog focuses on the Reversal Algorithm which is one of the optimal approaches to rotate an Array. In order to learn more about the Reversal Algorithm let’s give it a read.


The concept of the Reversal algorithm for ‘left rotation’ is that it reverses the last ‘r’ elements of a given array and reverses the remaining ‘r-n’ followed by reversing the complete array. 

Here the r is the rotation count of the array, and n is the array’s length. 

 

The main idea of the Reversal algorithm is to perform multiple in-place reversals to rotate a given array. We have to complete three setbacks with different starting and ending points to find the rotated array.

Algorithms

For left rotation, the Reversal algorithm would become:

As we discussed there are two different directions of rotation of the array. Let’s discuss the Left rotation, using the Reversal Algorithm.

In order to perform the Left Rotation using Reversal Algorithm,the first step is to reverse the first ‘r’ elements of the array and then reverse the remaining ‘n-r’ elements of the array followed by the reversal of the complete array.

Here r is the rotation count of the array, and n is the length of the given array.

 

ALGORITHM:

 

STEP 1: Start

 

STEP 2: Reverse the first ‘r’ elements.

 

STEP 3: Reverse the remaining ‘n-r’ elements.

 

STEP 4:  Reverse the entire array.

 

STEP 5: Stop 

 

Fn: reverse(arr,start,end) 

 

 

For right rotation, the Reversal algorithm would become:

Let’s now understand the right direction rotation using the Reversal Algorithm, the first step to perform right rotation using Reversal Algorithm is to reverse all the elements of the given array and then reverse the first ‘r’ elements followed by reversing the remaining n-r elements.

Here r is the rotation count of the array, and n is the length of the given array.

 

ALGORITHM:

 

STEP 1: Start

 

STEP 2: Reverse the array 

 

STEP 3: Reverse the first ‘r’ elements 

 

STEP 4:  Reverse the remaining ‘n-r’ elements

 

STEP 5: Stop 

 

Fn: reverse(arr,start,end) 

 

 

Let us consider an example to understand how does the Reversal Algorithm works, 

 

We are given an array arr[] = {1, 2, 3, 4, 5} and we are told to perform left array rotation when the given rotation count is 2.

 

Step 1: Reverse the first r elements. 

 

We are given r = 2. Therefore we will reverse the first two elements of the array.

 

 

Step 2: Reverse the remaining ‘n-r’ elements. Here n = 5 and r =2, we have to reverse the remaining three elements.

 

 

Step 3: Reverse the elements of the entire array.

 

 

The answer after left rotation is : 3,4,5,1,2

 

Calculating Time and Space Complexity

 

Let us find the Time complexity of the Reversal Algorithm.

We will find the time complexity of each step and then add the individual complexity to find the final result.

 

  • For reversing the first ‘r’ elements of the array, the time complexity is: O(r)
  • For reversing the remaining ‘n-r’ elements, the time complexity is: O(n-r)
  • For reversing the entire array, the time complexity is: O(n)

 

Let us combine the individual elements to find the time complexity of this algorithm.

 

  → O(r(1) + n(1) + n(1))

  →O(r+ 2n)

 

If n is very, very large, then drop r and the constant 2,

Therefore, O(n) is the time complexity of the reversal algorithm.

 

To find the Space Complexity of the Reversal Algorithm,

In a common reversal method, we use variables like start, arr, temp, end. 

These variables have fixed space at a given time, which means that the space will not increase with a change in the number of inputs. 

 

Therefore the auxiliary space complexity is constant which is denoted by O(1).

 

Implementation of the Algorithm 

We have the Java code explaining the implementation of the reversal algorithm.

 

public class Main

{

  public static void main (String[]args) {

    int[] arrayLeft = new int[]{ 12345 };

    int[] arrayRight = new int[]{ 12345 };

    //rotation count is 2

    int r = 2;      

    arrayLeft = rotateLeft (arrayLeft, r);

    arrayRight = rotateRight (arrayRight, r);

    System.out.println ("Array after left rotation : ");

    for (int i = 0; i < arrayLeft.length; i++) {

      System.out.print (" " + arrayLeft[i]);

    }

    System.out.println ();

    System.out.println ("Array after right rotation : ");

    for (int i = 0; i < arrayRight.length; i++) {

      System.out.print (" " + arrayRight[i]);

    }  

  }

  

  public static void reverse (int[]arr, int start, int end) { 

    while (start < end) {

      int temp = arr[start];

      arr[start] = arr[end];

      arr[end] = temp;

      start++;

      end--;

    }

  }

 

  public static int[] rotateLeft (int arr[], int r) { 

    r %= arr.length;

    //rotating the first r elements

    reverse (arr, 0, r - 1);  

    //rotating length-r elements

    reverse (arr, r, arr.length - 1); 

    //reversing the entire array

    reverse (arr, 0arr.length - 1); 

    return arr;

  }

  public static int[] rotateRight (int arr[], int r) { 

    r %= arr.length;

    //reversing the entire array

    reverse (arr, 0arr.length - 1);

    //rotating the first r elements 

    reverse (arr, 0, r - 1);  

    //rotating length-r elements

    reverse (arr, r, arr.length - 1);  

    return arr;

  }

}

 

 

OUTPUT

 

Array after left rotation : 

 3 4 5 1 2

Array after right rotation : 

 4 5 1 2 3

 

 

Frequently Asked Questions

  1. What is Reversal Algorithm?
    Ans-The main idea of this algorithm is to perform multiple in-place reversals to rotate a given array. We have to complete three reversals with different starting and ending points to receive the final rotated array.
     
  2. What is the time complexity of the Reversal Algorithm?
    Ans- The time complexity of the Reversal Algorithm is O(n), where n is the array’s length.
     
  3. How to perform left array rotation using the Reversal Algorithm?
    Ans- To perform left array rotation, reverse the first ‘r’ elements, then reverse the remaining ‘n-r’ elements of the array followed by the reversal of the complete array, where r is the rotation count of the array and n is the length of the array.
     

Key Takeaways

This article discussed how the reversal algorithm works and why is it used for Array Rotation. The article covers the approach of the array rotation algorithm.

It is used to rotate the elements of the arrays when we are given the number of rotations.

The Approach of the Reversal Algorithm uses multiple in-place reversals to rotate an entire array. Let us see the steps involved in the Algorithm.

  1. For the Left rotation, we will reverse the Array for the first r terms. Then we will reverse the remaining n-r terms followed by the reversal of the complete array.
  2. We will reverse the Array entire array for the Right rotation, and then the first ‘r’ elements will be reversed, followed by the remaining ‘n-r’ elements.
    Here, the ‘r’ is the rotation count, and the ‘n’ is the array’s length.

 

To understand Array Rotation better, we have a complete article. Give it a read to understand the different approaches used to rotate an Array.

 

Visit here to learn more about arrays. You can also practice similar problems on CodeStudio. If you liked this blog, share it with your friends.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think