What is array rotation?

Ans: Array Rotation is simply shifting the elements of the arrays to the next consecutive position. The array can be rotated clockwise or anticlockwise.

What is the time complexity of an array one by one rotation method?

Ans: The time complexity of the array one by one rotation method is O(Length_of_array * k)

How do you rotate an array clockwise?

Ans: If we want to perform clockwise rotation, the array elements are shifted to the left. The array is rotated to its left by shifting its element to a position before the same. In the left rotation, the first element is assigned to the last position of the array. In this approach, each element is rotated one by one using a for loop.

Program for Array Rotation in Java

Introduction

Array Rotation simply implies moving components of the array to the left or right or to directly by n position without debilitating the "bound of the array.” We can perform any number of array rotations and in both directions. We can perform both clockwise and anti-clockwise rotations in arrays.

Problem Statement

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 will be covering different approaches to the problem statement.

Types of Rotation

We have two types of rotations:

Left array rotation(Clockwise Rotation)
Right array rotation(Anticlockwise Rotation)

To understand the concept better, let’s take an example of an array arr = [20,30,40].

If we rotate this array to the left by one index, every element would be moved towards the start of the array that is (index zero) by one place, and in this course, the first element, 20, will be moved from the first index towards the last index. The rotate array will now look like [30,40,20].

Similarly, if we perform array rotation to the right on the same array by one element, every element will shift towards the end of the array, and the last element will be indexed to the first index.
The rotated array after the right rotation would look like [40,20,30]

Below is a sample Java program to illustrate Array Rotation. We have created two classes, precisely rotate left and rotate right, both of which take an array and number of rotations(k) as parameters.

LEFT ARRAY ROTATION:

The approach for the left rotation is an easy-to-understand method where the ‘n’ is the number of rotations that should be performed. The array is rotated to its left by shifting its element to a position prior to the same. In the left rotation, the first element is assigned to the last position of the array. In this approach, each element is rotated one by one using a for loop.

import java.util.Arrays;

class Main {

public static void main(String[] args) {

//Initialize array

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

//k determines the number of times an array is to be rotated

int k = 3;

System.out.println("Original Array");

//Displays the original array

System.out.println(Arrays.toString(arr));

//Calls the left rotation function

leftRotation(arr,k);

//Displays the rotated array

System.out.println("Reversed Array");

System.out.println(Arrays.toString(arr));

}

public static void leftRotation(int[] arr, int k) {

//checks for the base condition

if(k==0 || k%arr.length==0)

return;

k = k%arr.length;

//Rotate the given array by k times toward left

for(int i = 0 ; i<k ; i++) {

int firstele = arr[0];

for(int j = 0 ; j < arr.length - 1 ; j++) {

arr[j] = arr[j+1];

}

arr[arr.length-1] = firstele;

}

OUTPUT

Original Array:

[1, 2, 3, 4, 5]

Rotated Array:

[4, 5, 1, 2, 3]

Time complexity: O(n*k), where n is the number of elements in the array and k is the number of times we need to perform left rotation on the array. Since k can be at most n-1(k = k%n), the time complexity in the worst case is O(n^2).

Space Complexity: O(1)

RIGHT ARRAY ROTATION:

The approach for the right rotation is an easy-to-understand method where the ‘k’ is the number of rotations that should be performed. The array is rotated to right by shifting the elements of the arrays to the next element in the array. In right rotation, the last element of the array is added to the start of the array.

import java.util.Arrays;

class Main {

public static void main(String[] args) {

//Initialize array

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

//k determines the number of times an array is to be rotated

int k = 2;

System.out.println("Original Array");

//Displays the original array

System.out.println(Arrays.toString(array));

//Calls the right rotation function

rightRotation(array,k);

//Displays the rotated array

System.out.println("After right rotation Array");

System.out.println(Arrays.toString(array));

}

public static void rightRotation(int[] arr, int k) {

k = k%arr.length;

for(int i = 0; i < k; i++) {

int j, last;

//Stores the last element of the array

last = arr[arr.length-1];

for(j = arr.length-1; j > 0; j--) {

//Shift element of array by one

arr[j] = arr[j-1];

}

//Last element of array will be added to the start of array.

arr[0] = last;

}

OUTPUT

Original array:

[1, 2, 3, 4, 5]

Array after right rotation:

[4, 5, 1, 2, 3]

Space Complexity: O(1)

Approaches used for Array Rotation

There are many ways to perform rotation on an array, Some of them are:

By using a temp array.
By using Juggling Algorithm
By using Reversal Algorithm

By using a temp array

→ Algorithm:

Step 1: To store the first k elements in the temp array.

Step 2: Shift the left elements to the left.

Step 3: Append elements from the temp array to the main arr array.

The following is a Java program using the above approach.

import java.util.Arrays;

class Main {

public static void main(String[] args) {

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

int k = 2;

System.out.println("Original Array");

System.out.println(Arrays.toString(arr));

usingTempArr(arr,k);

System.out.println("Rotated Array using temp approach: ");

System.out.println(Arrays.toString(arr));

}

public static void usingTempArr(int[] arr, int k) {

if(k==0 || k%arr.length==0)

return;

k = k%arr.length;

int[] temp = new int[k];

for(int i=0;i<k;i++)

temp[i] = arr[i];

for(int i=0;i<arr.length-k;i++)

arr[i] = arr[k+i];

int j = 0;

for(int i = arr.length-k;i<arr.length;i++)

arr[i] = temp[j++];

}

OUTPUT

Original Array

[1, 2, 3, 4, 5]

Rotated Array using temp approach:

[3, 4, 5, 1,2]

Time Complexity: O(n), where n is the number of elements in the array.

Space Complexity: O(k), as we are using another temp array of size k where k denotes the number of rotations on the array.

By using the Juggling theorem

The juggling algorithm is an advanced version of rotating arrays one by one. This is one of the most efficient algorithms used for array rotation.

Step 1: Divide the array into sets S where S = GCD(length,k)

Step 2: For each set, shifting of elements will take place

Step 3: After all the elements have been shifted to the corresponding places, we will rotate the arrays for the given number of times.

Let’s consider an example,

If we have to rotate the below array by 2 positions, arr[] = [10,20,30,40,50,60]

Let’s see how the elements are rotated using the Juggling theorem,

We have the arr = { 10, 20, 30, 40, 50, 60 }

The algorithm divides the array into sets which are calculated using the Greatest common divisor/ HCF of the size and the rotating count given.

For this array, we know the size is 6 and we are given the rotation count as 2, the GCD(6,2) = 2. Therefore we would have two sets for the given array.

The two sets would be

Set 1: 10, 30, 50
Set 2: 20, 40, 60

This algorithm takes in count both the sets as individual arrays, therefore

both sets would be rotated twice.

Let’s see how would the sets be rotated :

As we have discussed, this would be set 1 as there are 2 sets to be taken into account for this array.
The second set would include the below elements.

The rotation would be done using the one by one method to rotate each

element and set 1 and set 2 would be considered two different individual arrays.

Let’s see how does the rotation actually work,
Set 1- Given in the below image, we can see that the elements 10, 30, and 50 are only considered for set 1 and they would be rotated.

After the rotation, we would have the array as

Similarly for Set 2, we will rotate the elements 20, 40, and 60 respectively.

After this step, we would have the array as,

Since the array is to be rotated twice, set 1 and set 2 will be rotated once more.
The important point to be noted here is the elements of set 1 would not be affected when set 2 is being rotated and similarly, the elements of set 2 would not be affected when set 1 is being rotated.

After the second rotation of set 1, the array would be,

Similarly, we would rotate set 2 again and this would be the final answer using

the juggling algorithm,

This is how the Juggling algorithm works and rotates the array. Let’s understand its implementation in Java.

import java.util.Arrays;

class Main {

public static void main(String[] args) {

int[] arr = {10,20,30,40,50,60};

int k = 2;

System.out.println("Original Array");

System.out.println(Arrays.toString(arr));

juggling(arr,k);

System.out.println("Rotated Array by Juggling Theorem");

System.out.println(Arrays.toString(arr));

}

public static void juggling(int[] arr, int k) {

if(k==0 || k%arr.length==0)

return;

k = k%arr.length;// number of rotations to be perfomed

int n = arr.length;//length of array

int gcd = gcd(n,k);

int j,d,temp;

// move i-th values of blocks

// gcd times the loop will iterate

for(int i= 0;i<gcd;i++) {

temp = arr[i];

j = i;

while(true) {

d = j+k;

// The element has to be shifted to its rotated position

if(d>=n)

d = d-n;

// The element is already in its rotated position

if(d==i)

break;

arr[j] = arr[d];

j = d;

}

arr[j] = temp;

}

//function to calculate gcd(n,k)

public static int gcd(int a, int b) {

if (b == 0)

return a;

else

return gcd(b, a % b);

}

OUTPUT

Original array :

[10, 20, 30, 40, 50, 60]

Rotated Array by Juggling Theorem:

[30, 40, 50, 60, 10, 20]

Time Complexity: O(n), where n is the number of elements in the array.

Space Complexity: O(1)

3. By using Reversal Algorithm

The Reversal algorithm uses multiple in-place reversals to rotate an entire array. Let us see the steps involved in the Algorithm.
We have a separate blog that covers how Reversal Algorithm works in detail, do give it a read.

4. By using Block Swap Approach

The concept of this algorithm is that it divides the given array into two sub-arrays, A and B, where A stores the first ‘r’ elements and B stores the rest ‘n-r’ elements.
We have a separate detailed blog that covers the Block Swap Approach in detail, do give it a read.

Frequently Asked Questions

What is array rotation?
Ans: Array Rotation is simply shifting the elements of the arrays to the next consecutive position. The array can be rotated clockwise or anticlockwise.
What is the time complexity of an array one by one rotation method?
Ans: The time complexity of the array one by one rotation method is O(Length_of_array * k)
How do you rotate an array clockwise?
Ans: If we want to perform clockwise rotation, the array elements are shifted to the left. The array is rotated to its left by shifting its element to a position before the same. In the left rotation, the first element is assigned to the last position of the array. In this approach, each element is rotated one by one using a for loop.
What is the reversal algorithm for array rotation?
Ans: The Reversal algorithm uses multiple in-place reversals to rotate an entire array. Let us see the steps involved in the Algorithm.

Key Takeaways

In this blog, we talked about the solution to the problem of Array Rotation.

We covered four different approaches to solve this problem.

The first approach was by declaring a temp array, in which we declared a
new temp array and stored the first k elements in it. We will then shift all the elements to their left position, and at the end, the appended elements were stored back in the main array due to the rotation.

The second approach was to rotate the elements of the array one by one. In this method, the first element was stored in a variable called first, and then the elements were shifted towards their left. The last element was assigned the first position.

The third approach was the Juggling Algorithm, which is an advanced version of rotating arrays one by one. This is one of the most efficient algorithms used for array rotation.

The fourth approach was using a Reversal Algorithm which uses multiple in-place reversals to rotate an entire array. We have a separate blog that covers the Reversal Algorithm for Array Rotation in detail to learn about the algorithm. Visit here to give it a read.
The fifth approach was by using the Block Swap Algorithm, in this the given array was divided into two sub-arrays A and B and was rotated accordingly. We have a separate blog that covers the Block Swap Algorithm in detail to learn about the algorithm. Visit here.

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.