Last Updated on September 22, 2023 by Mayank Dham
Rotate Array is the simple act of shifting an element of an array to the left, right, or directly by n positions without affecting the array’s "bounds." We can rotate an array in both directions an infinite number of times. In arrays, we may rotate in both clockwise and anticlockwise directions.
How to Rotate an Array in Java
Assume that we are given a straightforward array of five numbers, arr[] = [1,2,3,4,5] and that we are instructed to rotate the right side of the array by one.
Right, Rotate Array is briefly illustrated in the diagram above.
We’ll discuss various ways to tackle the issue description. Also, you can checkout How to reverse array in Java for better understanding of these type of similar problems.
Types of Rotate Array in Java
We have two types of rotations:
- Left Rotate Array(Clockwise Rotation)
- Right Rotate Array(Anticlockwise Rotation)
Let’s look at an array with the value [20,30,40] as an example to better grasp the idea.
Every element would move one position closer to the beginning of the array, which is index zero if we rotated this array to the left by one index. In this lesson, the first element, 20, will move from the first index to the final index. Now, the rotate array will appear as [30,40,20].
Similar to the previous example, if we rotate the same array to the right by one element, all elements will move to the end of the array and the last element will be indexed to the initial index.
After the correct rotation, the rotated array would resemble [40,20,30].
A Java example application that demonstrates Rotate Array is shown below. Our two classes, rotate left and rotate right, each has a number of rotations(k) parameter and accept an array as input.
Left Rotate Array
The procedure for the left rotation is a straightforward one, and ‘n’ stands for the recommended number of rotations. By moving an element to a position before the same, the array is rotated to the left. The array’s final position is given to the first member in the left rotation. Using a for loop, each element is rotated individually in this method.
Code Implementation:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5};
int k = 3;
System.out.println("Original Array");
System.out.println(Arrays.toString(arr));
leftRotation(arr,k);
System.out.println("Reversed Array");
System.out.println(Arrays.toString(arr));
}
public static void leftRotation(int[] arr, int k) {
if(k==0 || k%arr.length==0)
return;
k = k%arr.length;
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]
Reversed Array
[4, 5, 1, 2, 3]*Time Complexity: O(nk)**, where n is the array’s total amount of items and k is the number of times the array must be rotated to the left. Since k can only be n-1 (k = k%n), the worst-case temporal complexity is O(n2).
Space Complexity: O(1)
Right Rotate Array
The strategy for the appropriate rotation is a straightforward process, where k is the recommended number of rotations. By moving the array’s items to the following element, the array is rotated to the right. The array’s final member is appended to its beginning during the right rotation.
Code Implementation:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
int[] array = {1,2,3,4,5};
int k = 2;
System.out.println("Original Array");
System.out.println(Arrays.toString(array));
rightRotation(array,k);
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;
last = arr[arr.length-1];
for(j = arr.length-1; j > 0; j--) {
arr[j] = arr[j-1];
}
arr[0] = last;
}
}
} Output:
Original Array
[1, 2, 3, 4, 5]
After right rotation Array
[4, 5, 1, 2, 3]*Time complexity: O(nk)**, where n is the array’s total amount of items and k is the number of times the array must be rotated to the left. Since k can only be n-1 (k = k%n), the worst-case temporal complexity is O(n2).
Space Complexity: O(1)
Approaches used for Rotate Array
There are several methods for rotating an array, some of which include:
- By using a temp array.
- By using Juggling Algorithm
- By using Reversal Algorithm
By using a Temp Array
We will use a temp array for this method to rotate array.
Algorithm:
- To fill the temporary array with the first k entries.
- Move the left-most elements to the left.
- Add elements from the temp array to the primary array of arguments.
The Java program that uses the above strategy is shown below.
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
An improved variant of rotating arrays one by one is the juggling algorithm. One of the most effective Rotate Array methods is this one.
Algorithm
- Set the array into sets S with S = GCD(length,k) so that items will be shifted in each set.
- We will rotate the arrays for the specified amount of rotations when all the items have been relocated to their proper positions.
Take the following array’s rotation by two positions as an example: 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 method splits the array into sets based on the specified rotation count and greatest common factor/ HCF of the size.
Given that this array has a size of 6 and a rotation count of 2, the GCD(6,2) value for it is 2. Thus, with the given array, we would have two sets.
There would be two sets.
- Set 1: 10, 30, 50
- Set 2: 20, 40, 60
Each set would be rotated twice since this approach counts both sets as separate arrays.
Let’s examine the rotation of the sets:
- This would be set 1 because there are two sets to be considered for this array, as we have already established.
- The following components would form part of the second set.
Sets 1 and 2 would be treated as two separate individual arrays and the rotation would be carried out by rotating each element one at a time.
Let’s see how the rotation truly functions.
Set 1- The elements 10, 30, and 50 are only taken into account for set 1 and will be rotated, as seen in the graphic below.
The array would appear as follows after the rotation:
| 50 | 20 | 10 | 40 | 30 | 60 |
|---|
We will rotate the elements 20, 40, and 60 in the same manner for Set 2.
After this step, the array would look like,
| 50 | 60 | 10 | 20 | 30 | 40 |
|---|
Sets 1 and 2 will be rotated once more since the array has to be turned twice.
The key thing to remember in this situation is that neither the rotation of set 2 nor the rotation of set 1 would have any impact on the components of either set.
The array would be after set 1’s second rotation,
| 30 | 60 | 50 | 20 | 10 | 40 |
|---|
The final response using the juggling method would be this after rotating set 2 one more,
| 30 | 40 | 50 | 60 | 10 | 20 |
|---|
The Juggling algorithm rotates the array in this manner. Let’s see how Java implemented it.
Code Implementation:
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;
int n = arr.length;
int gcd = gcd(n,k);
int j,d,temp;
for(int i= 0;i<gcd;i++) {
temp = arr[i];
j = i;
while(true) {
d = j+k;
if(d>=n)
d = d-n;
if(d==i)
break;
arr[j] = arr[d];
j = d;
}
arr[j] = temp;
}
}
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)
By using Reversal Algorithm
The Reversal algorithm rotates a complete array by performing several in-place reversals. Let’s have a look at the algorithm’s steps.
By using the Block Swap Approach
This algorithm’s basic idea is to split the input array into two smaller arrays, A and B, where A saves the first "r" elements and B stores the remaining "n-r" elements.
Conclusion
We discussed the answer to the Rotate Array issue in this blog. We discussed four methods for solving this issue.
- The first method included creating a new temporary array and storing the first k entries in it. After that, we will move every element to the left, and because of the rotation, the added items were eventually put back in the main array.
- The array’s items were rotated individually in the second method. This approach involves shifting the items to the left after storing the first element in a variable named first. The first place was given to the last element.
- The Juggling Algorithm, an improved method of rotating arrays one at a time, was the third strategy. One of the most effective Rotate Array methods is this one.
- The fourth method rotates a full array using a Reversal Algorithm, which employs several in-place reversals.
- The fifth method involved rotating the provided array in accordance with splitting it into the two sub-arrays A and B using the Block Swap Algorithm.