How to Rotate an Array in Java

In this blog, we will learn what exactly array rotation is. And how to rotate an array either in the left or the right direction. Here rotation only means shifting the elements of the array in the desired direction.

Example

Explanation

Initially, the array was [1, 2, 3, 4, 5], if we rotate the array once (k=1) towards the right, the element will shift from the index 0 to index 1 Similarly, we need to shift all elements towards the right, which means the last element will end up with at the first position.

Now after the first rotation – Arr[] = [5, 1, 2, 3, 4]

If we rotate on more time – Arr[] = [4, 5, 1, 2, 3] -> k = 2

Similarly, if we want to rotate the array towards the left. In that case, we have to shift the elements to the left, the element will shift from index 1 to index 0, and the other elements as well making the first element the last element of the array.

How to solve it

There are many kinds of approaches, but we will only be seeing two approaches in this blog They are – 

1. Using the temp array
2. By reversing the Array

Approach 1 – By using the Temp Array

The idea is simple, we will create a new array of size k and store the elements equal to k from either start or the end of the array depending upon the type of rotation we are doing, and then put them back in the original array where they were supposed to be placed after rotation. Check the example given below in which we are rotating k times towards left, to understand the approach better.

Example

Input arr[] = [1, 2, 3, 4, 5] 

k = 2 

• Store the first k elements in a temp array: temp[] = [1, 2]
• Shift rest of the elements(according to the given data/ question): arr[] = [3, 4, 5,]
• Store back the k elements: arr[] = [3, 4, 5, 1, 2]

Approach

1. Create a new array called temp of length k – the number of times we have to rotate the array
2. Store either the first k elements or the last k elements depending upon the type of rotation 
3. Move the rest of the elements either towards the 0th index or the last index.
4. Copying the elements stored from the temp array to the original array at their respective indexes.

package com.Tekolio.Arrays;
  
import java.util.Arrays;
  
public class Rotate_an_Array {
   public static void main(String[] args) {
       int[] A = {1, 2, 3, 4, 5};
       int[] a = {1, 2, 3, 4, 5};
       int n = A.length;
       int k = 3 % n;
       rotateArray(A, 0, n - 1);
       rotateArray(A, 0, k - 1);
       rotateArray(A, k, n - 1);
   }
    public static void rotateArray(int[] A, int start, int end) {
        while(start < end) {
           int temp = A[start];
            A[start] = A[end];
            A[end] = temp;
            start++;
            end--;
        }
        System.out.println(Arrays.toString(A));
    }
}

Output

A = [3, 4, 5, 1, 2]

Time complexity: O(N), Auxiliary Space: O(N)

In the above code, we have used System.arraycopy method to copy the k elements from the array and put them back at their desired position after rotation.

The code discussed above is for rotating the array towards the left, we can also do the same thing for rotating the array in the right direction as well, we just have to change the index numbers in both the loop and the System.arraycopy method as shown.

 // Copying first temp element in array temp
 System.arraycopy(A, 0, temp, 0, k);
 // Moving the rest elements
 for(int i=k; i<n; i++) {
 	A[i-k] = A[i];
}
// Copying the temp array element in original array
System.arraycopy(temp, 0, A, n-k, k);

We have used the modulus operator in the value of k so that we always have a value to rotate the array between 0 and the length of the array. Like if the value of k = 6, now the value of k is more than the length of the array, in this case, the modulus operator comes into play – 6%5 = 1. Thus we have to rotate the array once. 

The same process should be followed if the value of k is negative.

Method 2 – By Reversing the Array

The idea is to first reverse the whole array and then reverse it again but in parts. The first part will be from the 0th index till the kth index while the second part contains the rest of the elements.

Example

Input : A = [1, 2, 3, 4, 5], k=2

Reversing the whole array – A = [5, 4, 3, 2, 1]

Reversing in parts – A = [4, 5, 1, 2, 3]

Here we are not using any additional space like in the above code, thus the space complexity becomes O(1) while the time complexity remains unchanged.

Approach

1. Reverse the whole Array 
2. Divide the array into two parts, from 0 to k-1 and from k to n-1
3. Reverse these two parts individually and we have our rotated array

package com.Tekolio.Arrays;
 
import java.util.Arrays;
 
public class Rotate_an_Array {
   public static void main(String[] args) {
       int[] A = {1, 2, 3, 4, 5};
       int[] a = {1, 2, 3, 4, 5};
       int n = A.length;
       int k = 3 % n;
       rotateArray(A, 0, n - 1);
       rotateArray(A, 0, k - 1);
       rotateArray(A, k, n - 1);
   }
    public static void rotateArray(int[] A, int start, int end) {
        while(start < end) {
           int temp = A[start];
            A[start] = A[end];
            A[end] = temp;
            start++;
            end--;
        }
        System.out.println(Arrays.toString(A));
    }
 

Output

A = [3, 4, 5, 1, 2]

Time Complexity: O(n)    Auxiliary Space: O(1)

We have already discussed the approach in brief, and it is also clear from the code itself that we are reversing the array two times, a full reversal at the beginning and a reversal by parts at the end to get our desired array. 

And for that, we have created a separate class called rotateArray that deals with the reversing part of the program. This class takes three parameters  – 

1. The original array
2. The starting index
3. The ending index

Which we have provided it from the main class from which we have called this class for all the three conditions of reversing the whole array to rotate it towards the left.

What if we want to rotate the array in the right direction? 

We have to first deal with reversing the array in parts and then reverse the whole array to get the desired array. Check the code below – 

 rotateArray(A, 0, k-1);
 rotateArray(A, k, n-1);
 rotateArray(A, 0, n-1);

Conclusion

In this blog, we have seen what it means to rotate an array and how many types of array rotations are there with different ways to do each of them. 

There can be many more strategies out there through which this question can be solved, but the minimum time complexity and the space complexity will always be O(n) and O(1) as we do have to traverse the array once to shift all the elements either towards the right or left depending upon which type of rotation we are doing.

This question was asked by many tech companies like Microsoft and Amazon and also can become pretty difficult sometimes if the value of k exceeds the length of the array or is negative.