Software Key Tutorial
.
In the realm of computer programming, arrays play a significant role. Arrays are at the core of many data manipulation operations in programming, and array rotation is an interesting process. In particular, array rotation is a dynamic operation that rearranges the array's elements, with the last element looping back to the beginning.
This article dives into a specific operation on arrays, the rotate array. Learn how to rotate the array to the right by k steps, which can be thought of as a circle moving in a straight line. We'll explore these operations in the context of one of the most widely used programming languages, Java.
When we talk about array rotation in Java, we refer to the process of moving each element in the array to its adjacent position, such that the last element moves to the first position. This rotation can be either to the left or the right.
An array can be envisioned as a circular train, with each carriage representing an array element. Rotating the array is just like moving this circular train by a certain number of steps in a specific direction, either left or right.
In Java, arrays are static entities. This means that once the size of an array is declared, it remains consistent. This necessitates the need to be cautious while performing operations such as array rotation.
Let's consider an array arr[] = {1,2,3,4,5} and we want to rotate it to the right by two steps. After the rotation, our array would look like arr[] = {4,5,1,2,3}.
java
int[] arr = {1,2,3,4,5};
int k = 2;
rotateArray(arr, k);Left Rotation
In left rotation, every element is shifted to its left, and the first element is placed at the end of the array. For instance, if we have an array {1,2,3,4,5}, after one step of left rotation, the array becomes {2,3,4,5,1}.
Right Rotation
In right rotation, every element is shifted to its right, and the last element is placed at the beginning of the array. So, our example array {1,2,3,4,5} becomes {5,1,2,3,4} after one step of right rotation.
Let's discuss some approaches to rotating an array in Java.
Approach 1: Using temp array
This method creates a temporary array of size k rotations. The last k elements are stored in this temp array; the original array is shifted right by k steps; and the elements from the temp array are placed at the beginning of the original array.
java
void rotateArray(int arr[], int k) {
int n = arr.length;
int[] temp = new int[k];
for(int i = 0; i < k; i++)
temp[i] = arr[n-k+i];
for(int i = n-k-1; i >= 0; i--)
arr[i+k] = arr[i];
for(int i = 0; i < k; i++)
arr[i] = temp[i];
}Let's take an example array to attain a specific output that elucidates the concept further. Consider arr[] = {1, 2, 3, 4, 5, 6, 7} and rotate it by k = 3 steps.
The steps of the code are as follows:
1. An array of size 'k' is created: temp[] = {0, 0, 0}
2. The last 'k' elements of the original array are copied into the new array: temp[] = {5, 6, 7}
3. The remaining elements of the original array are shifted right by 'k' positions: arr[] = {1, 2, 3, 1, 2, 3, 4}
4. The elements from the temporary array are copied back to the first 'k' positions of the original array: arr[] = {5, 6, 7, 1, 2, 3, 4}
Thus, the output of the rotateArray function would be: {5, 6, 7, 1, 2, 3, 4}, which is the original array rotated to the right by 3 steps.
This Java function works in place (i.e., it modifies the original array). The time complexity of this function is O(n), as each element is moved exactly once. However, it has a space complexity of O(k) due to the extra space used to create the temporary array.
Advantages:
Simplicity: This strategy is simple and easy to grasp, making it perfect for novices.
Performance: The temporal complexity is O(n), which is quite efficient.
Disadvantages:
Space Complexity: This method creates a temporary array by using extra space. If the array to rotate is huge, this method may require a significant amount of extra RAM.
Time Complexity: O(n)
Copying the last 'k' elements to a temp array: O(k)
Shifting the first 'n-k' elements to the right by 'k' positions: O(n-k)
Copying the 'k' elements from the temp array to the beginning of the original array: O(k)
Hence, combined, it results in O(n).
Space Complexity: O(k)
A temporary array of size 'k' is used.
Approach 2: Rotate Array One by One
This approach rotates an array by one position at a time. It works by storing the last element of the array in a temporary variable and then shifting all of the other elements of the array from one position to the right. Finally, the temporary variable is placed at the beginning of the array. This process is repeated k times to rotate the array to the right by k positions.
java
void rotateArray(int arr[], int k) {
for(int i = 0; i < k; i++)
rotateByOne(arr);
}
void rotateByOne(int arr[]) {
int n = arr.length;
int temp = arr[n-1];
for(int i = n-1; i > 0; i--)
arr[i] = arr[i-1];
arr[0] = temp;
}Let's explain this with an example array, arr[] = {1, 2, 3, 4, 5, 6, 7} and rotate it by k = 3 steps.
The steps of the code are as follows:
1. For each step from 0 to 'k', the function rotateByOne is called.
2. Inside the rotateByOne function, the last element of the array is stored in 'temp': temp = 7
3. All elements of the array are shifted right by one position: arr[] = {7, 1, 2, 3, 4, 5, 6}
4. The 'temp' value (the original last element) is placed at the start of the array: arr[] = {7, 1, 2, 3, 4, 5, 6}
After the initial rotation (k=1), the array appears as follows: {7, 1, 2, 3, 4, 5, 6}
Following the second rotation (k=2), the array appears as follows: {6, 7, 1, 2, 3, 4, 5}
Following the third rotation (k=3), the array appears as follows: {5, 6, 7, 1, 2, 3, 4}
Thus, the output of the rotateArray function would be: 5, 6, 7, 1, 2, 3, 4, which represents the original array rotated three steps to the right.
This Java function modifies the array in place, modifying the original array directly. The time complexity is O(n*k) because, for each rotation, n array elements are shifted. However, the space complexity is O(1) since only a single transient variable requires additional space.
Advantages:
Space Efficient: As it operates on the original array, this approach requires no additional space.
Disadvantages:
Time Complexity: This method has a time complexity of O(n*k), where 'n' is the length of the array and 'k' is the number of rotations. If 'k' is large, this approach might take longer.
Time Complexity: O(n*k)
In each of the 'k' iterations, 'n' elements of the array are shifted: k * O(n) = O(n*k).
Space Complexity: O(1)
Only a single temporary variable is used for storing the element that's being shifted.
Approach 3: Juggling Algorithm
The juggling algorithm rotates arrays efficiently. It rearranges the array by moving elements. This method divides the array into sets equal to the GCD of n and k and moves elements within them.
java
void rotateArray(int arr[], int k) {
int n = arr.length;
int gcd = findGcd(n, k);
for(int i = 0; i < gcd; i++) {
int temp = arr[i];
int j = i;
while(true) {
int l = j + k;
if(l >= n)
l = l - n;
if(l == i)
break;
arr[j] = arr[l];
j = l;
}
arr[j] = temp;
}
}
int findGcd(int a, int b) {
if(b == 0)
return a;
else
return findGcd(b, a % b);
}Consider the array arr[] = [1, 2, 3, 4, 5, 6, 7] as an example and rotate it by k = 3 steps.
The steps of the code are as follows:
1. Calculate the Greatest Common Divisor (GCD) of the array length 'n' and the number of rotations 'k': gcd = 1.
2. Each element from 0 to gcd undergoes a rotation within its respective set. The current element is stored in the 'temp' variable. temp = 1
3. A while iteration that shifts the elements within the set is initiated. If the index 'l' is greater than the length of the array 'n', it returns to the beginning of the array: arr[] = {4, 2, 3, 1, 5, 6, 7}
4. Once all elements of the set have been rotated, the 'temp' value (the original first element of the set) is appended to the end of the rotated set: arr[ = 4, 2, 3, 1, 5, 6, 7
5. This is repeated for each set (there is only one set in this case).
After the initial set (gcd=1), the array appears as follows: {4, 2, 3, 1, 5, 6, 7}
Thus, the output of the rotateArray function would be: 4, 2, 3, 1, 5, 6, 7, which represents the original array rotated three steps to the right.
This function modifies the array in place, modifying the original array directly. This function has an O(n) time complexity because each element is moved precisely once. The space complexity is O(1), as only a few variables require additional storage space.
Advantages:
Space-efficient: Like the second approach, this one works on the original array and doesn't need any extra space.
Performance: The juggling algorithm has a time complexity of O(n), which makes it faster than the other methods when 'k' is big.
Disadvantages:
Complexity: This method can be hard to understand and use, especially for people who are just starting.
Time Complexity: O(n)
Each element is moved exactly once.
Space Complexity: O(1)
A few variables are used for the loops and for storing temporary data, but no additional data structures are needed.
Approach 4: Reversing an Array
The rotate array operation can also be done by reversing parts of the array. First, we reverse the elements from index 0 to n-k-1. Then, we reverse the elements from n-k to n-1. Finally, we reverse the whole array.
java
void rotateArray(int arr[], int k) {
int n = arr.length;
reverse(arr, 0, n-k-1);
reverse(arr, n-k, n-1);
reverse(arr, 0, n-1);
}
void reverse(int arr[], int start, int end) {
while(start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}Let's demonstrate this by rotating the array arr[] = [1, 2, 3, 4, 5, 6, 7] by k = 3 steps.
The code's stages are as follows:
The initial portion of the array, from 0 to 'n-k-1', is inverted: arr[] = 4, 3, 2, 1, 5, 6, 7
The second portion of the array is inverted, from 'n-k' to 'n-1': arr[] = 4, 3, 2, 1, 7, 6, 5
The array is then inverted entirely: arr[] = 5, 6, 7, 1, 2, 3, 4
Thus, the output of the rotateArray function would be: 5, 6, 7, 1, 2, 3, 4, which represents the original array rotated three steps to the right.
This Java function modifies the array in place, modifying the original array directly. The complexity in terms of time is O(n), as each element is moved precisely once. The space complexity is O(1) because the algorithm requires only a few variables to temporarily store data.
Advantages:
Space-efficient: This method doesn't take up any extra room.
Performance: It works better than the second method because it takes O(n) time to do.
Disadvantages:
Complexity: This method is harder to understand and use than the first two because it is similar to the juggling program.
Time Complexity: O(n)
Each part of the array is reversed once: O(n/2 + n/2 + n/2) = O(3n/2) which is effectively O(n).
Space Complexity: O(1)
Only a couple of temporary variables are used for the reverse operation.
Understanding how to rotate array in Java and other programming languages is a fundamental skill. It is a topic that often comes up in technical interviews and coding tests. We have explored four different methods to achieve array rotation, each with its distinct benefits and applications. With a solid grasp of these techniques, you're now ready to tackle any problems related to array rotation in Java.
1. How can you rotate an array without using any additional space?
Rotating an array without using any additional space can be done using the juggling algorithm or by reversing an array.
2. What are the applications of array rotation?
Cyclic data structures, data encryption, and picture rotation methods use array rotation. It's employed in data analysis algorithms too.
3. How do array rotation and reversal differ?
Rotation rotates all elements left or right, while array reversal swaps elements at opposite ends until they meet in the middle, reversing the array's order.
Leave a Reply
Your email address will not be published. Required fields are marked *