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 rightside 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 â€˜rnâ€™ 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 inplace 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 â€˜nrâ€™ 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 â€˜nrâ€™ 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 nr 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 â€˜nrâ€™ 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 â€˜nrâ€™ 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.