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.
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[]{ 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
|
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.
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.
Comments
No comments yet
Be the first to share what you think