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.

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.

Table of contents

Introduction

Algorithms

2.1.

For left rotation, the Reversal algorithm would become:

2.2.

For right rotation, the Reversal algorithm would become:

Calculating Time and Space Complexity

Implementation of the Algorithm

Frequently Asked Questions

Key Takeaways

Last Updated: Mar 27, 2024

Reversal Algorithm for Array Rotation

Q: 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.

Author Rubleen Kaur Hanspal

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.

Must Read, Array Implementation of Queue and Rabin Karp Algorithm

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

Also see, Morris Traversal for Inorder.

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

Prims and Kruskal Algorithm

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[]{ 1, 2, 3, 4, 5 };

int[] arrayRight = new int[]{ 1, 2, 3, 4, 5 };

//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, 0, arr.length - 1);

return arr;

}

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

r %= arr.length;

//reversing the entire array

reverse (arr, 0, arr.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

Also, read - Kadane's Algorithm

Must Read C Program to Reverse a Number

Frequently Asked Questions

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

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

Check out the following problems -

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

Live masterclass

Master PowerBI using Netflix Data

by Ashwin Goyal, Product @ HRS Groups, Ex - Udaan, OYO

10 Sep, 2024

01:30 PM

305+ registered

View more events