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
dtimes, wheredis 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].
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
dto store the elements that need to be rotated. - We copy the first
delements 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
reversemethod 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
dto the last index. - Finally, we reverse the entire array, effectively rotating it left by
dpositions.
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.
You can download the full source code of this example here: Rotate Arrays in Java
