1.
Introduction
2.
Algorithms
2.1.
For left rotation, the Reversal algorithm would become:
2.2.
For right rotation, the Reversal algorithm would become:
3.
Calculating Time and Space Complexity
4.
Implementation of the Algorithm
5.
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Reversal Algorithm for Array Rotation

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

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

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

Read More - Time Complexity of Sorting Algorithms

## Implementation of the Algorithm

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

Must Read  C Program to Reverse a Number

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.

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