Rotate Arrays in Java (original) (raw)

In Java, array rotation refers to shifting the elements of an array by a specified number of positions. This operation can be performed in either direction: clockwise (right rotation) or counter-clockwise (left rotation). Array rotation finds applications in various domains such as algorithm design, data manipulation, and cryptography. This article will explore different approaches to performing array rotation in Java.

1. Example of Array Rotation

To illustrate an example of array rotation, let’s manually perform an array rotation on the array [1, 2, 3, 4, 5] by shifting the elements to the left by 2 positions.

Initial Array:

[1, 2, 3, 4, 5]

Step 1: Shifting elements individually

We’ll start by moving each element one position to the left.

Move 1 to the end:

[2, 3, 4, 5, 1]

Move 2 to the end:

[3, 4, 5, 1, 2]

Step 2: Final Rotated Array

After shifting each element by 1 position for 2 times, we get the final rotated array:

[3, 4, 5, 1, 2]

Summary of illustration:

Initial: [1, 2, 3, 4, 5] Step 1: [2, 3, 4, 5, 1] Step 2: [3, 4, 5, 1, 2] (Final)

This example shows a manual illustration of array rotation by shifting each element individually.

2. Brute Force Approach

The simplest method for array rotation involves shifting each element of the array one position to the left or right, depending on the direction of rotation. While this approach is straightforward, it may not be the most efficient for large arrays, as it requires shifting elements individually.

2.1 Example

public class ArrayRotation {

public static void rotateLeft(int[] arr, int d) {
    int n = arr.length;
    for (int i = 0; i < d; i++) {
        int temp = arr[0];
        for (int j = 0; j < n - 1; j++) {
            arr[j] = arr[j + 1];
        }
        arr[n - 1] = temp;
    }
}

public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    int rotations = 2;
    rotateLeft(array, rotations);
    for (int num : array) {
        System.out.print(num + " ");
    }
}

}

2.2 Explanation

This approach is the simplest method for array rotation, where each array element is shifted one position at a time.

We iterate over the array d times, where d is the number of rotations.
For each rotation, we store the first element of the array in a temporary variable.
Then, we shift each element of the array to the left by one position using a nested loop.
Finally, we assign the temporary variable to the last element of the array.

2.2.1 Time Complexity

Time complexity: O(n_×_d)
- n is the number of elements in the array.
- d is the number of rotations.
For each rotation, we need to shift n elements of the array, resulting in a time complexity of O(n).
Since we perform d rotations, the overall time complexity is O(n_×_d).

2.2.2 Space Complexity

Space complexity: O(1)
We only use a constant amount of extra space for storing temporary variables during the rotation process.

2.2.3 Output

After rotating the array left by 2 positions using the Brute Force Approach, the output is [3, 4, 5, 1, 2].

Fig 1: Output – Java Arrays Rotation using Brute Force Approach

3. Using Temporary Array

Another approach involves using an auxiliary array to store the rotated elements. This method is simple to implement and has a time complexity of O(n), where n is the number of elements in the array.

3.1 Example

public class RotateWithTemporaryArray {

public static void rotateLeft(int[] arr, int d) {
    int n = arr.length;
    int[] temp = new int[d];
    for (int i = 0; i < d; i++) {
        temp[i] = arr[i];
    }
    for (int i = d; i < n; i++) {
        arr[i - d] = arr[i];
    }
    for (int i = 0; i < d; i++) {
        arr[n - d + i] = temp[i];
    }
}

public static void main(String[] args) {
    int[] array = {2, 4, 6, 8, 10};
    int rotations = 3;
    rotateLeft(array, rotations);
    for (int num : array) {
        System.out.print(num + " ");
    }
}

}

3.2 Explanation

In this method, we use an auxiliary array to store the rotated elements.

We create a temporary array of size d to store the elements that need to be rotated.
We copy the first d elements of the original array into the temporary array.
We shift the remaining elements of the original array to the left.
Finally, we copy the elements from the temporary array back to the end of the original array to complete the rotation.

3.2.1 Time Complexity

Time complexity: O(n)
We copy the first d elements to the temporary array, which requires O(d) operations.
Shifting the remaining elements of the array requires O(n_−_d) operations.
Copying the elements from the temporary array back to the original array also requires O(d) operations.
Overall, the time complexity is O(n).

3.2.2 Space Complexity

Space complexity: O(d)
We create a temporary array of size d to store the rotated elements.

3.2.3 Output Explanation

The initial array is [2, 4, 6, 8, 10].
After rotating the array left by 3 positions using the approach with a Temporary Array, the output is:

8 10 2 4 6

4. Reversal Algorithm

The reversal algorithm is a more efficient approach for array rotation. It involves reversing the elements of the array in segments and then reversing the entire array.

4.1 Example

public class RotateArrayWithReverseAlgorithm {

public static void reverse(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

public static void rotateLeft(int[] arr, int d) {
    int n = arr.length;
    reverse(arr, 0, d - 1);
    reverse(arr, d, n - 1);
    reverse(arr, 0, n - 1);
}

public static void main(String[] args) {
    
    int[] array = {3, 6, 9, 12, 15, 18};
    int rotations = 3;
    rotateLeft(array, rotations);
    for (int num : array) {
        System.out.print(num + " ");
    }
}

}

4.2 Explanation

The reversal algorithm involves reversing segments of the array and then reversing the entire array.

We define a reverse method that takes the array and two indices as parameters and reverses the elements between those indices.
To rotate the array left, we first reverse the elements from index 0 to d-1.
Next, we reverse the elements from index d to the last index.
Finally, we reverse the entire array, effectively rotating it left by d positions.

4.2.1 Time Complexity

Time complexity: O(n)
Reversing a segment of the array requires O(n/2) operations.
Since we reverse the array twice and perform a total of three reversals, the time complexity remains linear, O(n).

4.2.2 Space Complexity

Space complexity: O(1)
Similar to the brute force approach, we only use a constant amount of extra space for temporary variables.

4.2.3 Output Explanation

The array [3, 6, 9, 12, 15, 18] is initialised.
After rotating the array left by 3 positions using the Reversal Algorithm, the output is:

12 15 18 3 6 9

5. Conclusion

In conclusion, while all three methods explored in this article achieve array rotation, the reversal algorithm and using a temporary array offer better time complexity than the brute force approach. However, the space complexity of using a temporary array is higher compared to the other two methods.

Finally, the choice of method depends on factors such as the size of the array, the number of rotations required, and the trade-offs between time and space complexities. By understanding and implementing these algorithms, we can efficiently rotate arrays in our Java programs.

6. Download the Source Code

This was an article on how to Rotate Arrays in Java.

Download
You can download the full source code of this example here: Rotate Arrays in Java

Omos holds a Master degree in Information Engineering with Network Management from the Robert Gordon University, Aberdeen. Omos is currently a freelance web/application developer who is currently focused on developing Java enterprise applications with the Jakarta EE framework.