Algorithm for Rotation of an Array by D Positions to the Left:

3.1.2.

Pseudocode for Rotation of an Array by D Positions to the Left

3.1.2.1.

Explanation:we have a row of numbered boxes again, like [1, 2, 3, 4, 5, 6]. This time, you want to move the boxes to the left by two steps.Here's how we do it:

3.1.2.2.

Code:

3.2.

Java

3.2.1.

Output

3.2.2.

Time Complexity:

3.2.3.

Space Complexity:

3.3.

2. Right Array Rotation

3.3.1.

Algorithm for Rotation of an Array by D Positions to the Right:

3.3.2.

Pseudocode for Rotation of an Array by D Positions to the Right:

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

What is Java Array Rotation

Java Array Rotation is the process of rearranging the elements of an array by shifting each element by a specified number of positions to the right or left. This can help with tasks like circular shifting, sorting, and reordering array elements.

If we rotate the array by two positions to the right, the new array would be: [2, 1, 5, 4, 3]. In this example, the elements of the array are shifted two positions to the right, and the elements that exceed the array length are brought back to the beginning.

Array rotation is a common operation in programming and is used in many applications, such as creating circular buffers, manipulating images, or solving algorithmic problems.

Types of Array Rotation in Java

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.

Recommended: Try the Problem yourself before moving on to the solution

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

Algorithm for Rotation of an Array by D Positions to the Left:

Input: Given an array of size n and an integer D representing the number of positions to rotate to the left.

Create a Temporary Array: Create a temporary array temp of size D to store the first D elements of the original array.

Copy First D Elements to Temp: Iterate from index i = 0 to D - 1. Copy arr[i] to temp[i] for each index I. This step stores the first D elements of the original array in the temp array.

Shift Elements to the Left: Starting from index i = 0, move each element to the left by D positions. This step "pushes" the elements to the left, and the D elements in temp will end up at the end of the array.

Copy Temp Elements to the End: Iterate from index i = n - D to n - 1. For each index I, copy temp[i - (n - D)] to arr[i]. This step copies the elements from the temporary array temp to the end of the original array.

The array is Rotated: After these steps, the array arr will be rotated to the left by D positions.

Pseudocode for Rotation of an Array by D Positions to the Left

function leftRotate(arr, n, D):
temp = new array of size D
// Copy the first D elements to temp
for i from 0 to D - 1:
temp[i] = arr[i]
// Shift the remaining elements to the left by D positions
for i from 0 to n - D - 1:
arr[i] = arr[i + D]
// Copy elements from temp to the end of arr
for I from n - D to n - 1:
arr[i] = temp[i - (n - D)]

Explanation: we have a row of numbered boxes again, like [1, 2, 3, 4, 5, 6]. This time, you want to move the boxes to the left by two steps. Here's how we do it:

Pick the First Boxes: Pick the first two boxes, 1 and 2.

Shift the Rest: Slide the remaining boxes to the left by two spots. This means each box moves two steps to the left to make room.

Place the Held Boxes: Put the boxes you were holding (1 and 2) at the end in the empty spots created by sliding. They'll be at the end of the row now. Your boxes are now rotated to the left by two steps. So, [1, 2, 3, 4, 5, 6] becomes [3, 4, 5, 6, 1, 2]. In the pseudocode, arr represents the array you're rotating, n is its size, and D is the number of positions to turn. The algorithm copies the first D elements to a temporary array, shifts the remaining elements to the left, and then places the copied elements back at the end.

Code:

Java

Java

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; } } }

You can also try this code with Online Java Compiler

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

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.

Algorithm for Rotation of an Array by D Positions to the Right:

Input: Gives an array of size n and an integer D for representing the number of positions to rotate to the right.

Calculate Effective Rotation: Calculate k = D % n to handle cases where D is larger than the array length.

Reverse the Entire Array: You can achieve this by swapping elements from the beginning with elements from the end of the array. It gradually moves towards the center.

Reverse the First K Elements: This effectively brings the k-rotated elements back to their original order.

Reverse the Remaining Elements: This restores the order of the remaining elements.

The array is Rotated: After these steps, the array will be rotated to the right by D positions.

Pseudocode for Rotation of an Array by D Positions to the Right:

function reverseArray(arr, start, end):
while start < end:
swap(arr[start], arr[end])
start = start + 1
end = end - 1
function rightRotate(arr, n, D):
k = D % n
reverseArray(arr, 0, n - 1)
reverseArray(arr, 0, k - 1)
reverseArray(arr, k, n - 1)

In this pseudocode, reverseArray is a function to reverse the elements of an array between the start and end. The rightRotate function implements the algorithm.

Code:

Java

Java

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; } } }

You can also try this code with Online Java Compiler

Original array:
[1, 2, 3, 4, 5]
Array after right rotation:
[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).

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

Rotate Element One by One

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.

Java

Java

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++]; } }

You can also try this code with Online Java Compiler

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

50

20

10

40

30

60

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

After this step, we would have the array as,

50

60

10

20

30

40

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,

30

60

50

20

10

40

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

30

40

50

60

10

20

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

Java

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); } }

You can also try this code with Online Java Compiler

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.

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.

Rotate Element One by One

This approach involves repeatedly moving each element in the array to its next position in a circular manner. This is done by shifting elements one position to the right (or left) k times, where k is the number of rotations desired.

Frequently Asked Questions

What is the formula for array rotation?

Iterate over the array. Apply formula arr[i]=arr[i+1] for array rotation. Add first element of the array to the end.

How do you find if an array is rotated?

To determine if an array is rotated, compare the first and last elements. If the last is smaller, the array is rotated. Alternatively, find the pivot point, where the element is smaller than its predecessor, indicating the rotation.

How to remove 1 from an array in Java?

To remove 1 from an array, create a new array with size-1. Now move through the original array, copying elements except for the element with value 1. Assign new array to the original array variable.

What is the use of array rotation?

The use of array rotation is sometimes we want the array to rotate in specific order to solve some problems like RUBIX CUBE is the best example I can think of for the practical uses of array rotation while you rotate one face of it, it affects each block like each data stored in the array when gets rotated to 90 degrees or 180 or 270 like that.

Conclusion

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.