Write a Java program to rotate an array to the left or right by n steps is a frequently asked Java interview question because it tests both problem-solving skills and understanding of array manipulation.
For example, if your array is– {1,2,3,4,5,6,7,8}
- Rotating the array 2 steps to the right results in {7,8,1,2,3,4,5,6}.
- Rotating the array 2 steps to the left gives {3,4,5,6,7,8,1,2}.
Array rotation program- Solution
This tutorial provides two efficient solutions for the Array Rotation Java Program.
- Using a temporary array and System.arraycopy() for faster copying. See example.
- Rotating elements one by one using loops, which is simple but less efficient for large arrays. See example.
Array rotation program- Using temp array
Solution using temporary array works as follows-
- Create a temporary array having the same length as the original array.
- If you have to rotate by 2 steps i.e. n=2 then copy n elements to a temporary array.
- Shift rest of the elements to the left or right based on rotation requirement.
- Copy elements from the temp array to the original array in the space created by shifting the elements.
In the program we actually copy all the elements to the temp array and then copy back to original array.
public class ArrayRotation {
public static void main(String[] args) {
int[] numArr={1,2,3,4,5,6,7,8};
//rotateLeft(numArr, 4);
rotateRight(numArr, 3);
}
private static void rotateLeft(int[] numArr, int steps){
// create temp array
int[] temp = new int[numArr.length];
// copy elements to the temp array
for(int i = 0; i < steps; i++){
temp[(numArr.length-steps)+ i] = numArr[i];
}
// copy rest of the elements from the original array
int i = 0;
for(int j = steps; j < numArr.length; j++, i++){
temp[i] = numArr[j];
}
//copy from temp to original
System.arraycopy(temp, 0, numArr, 0, numArr.length);
System.out.println("Array after left rotation- " + Arrays.toString(numArr));
}
private static void rotateRight(int[] numArr, int steps){
// create temp array
int[] temp = new int[numArr.length];
// copy elements to the temp array
for(int i = 0; i < steps; i++){
temp[i] = numArr[(numArr.length-steps)+ i];
}
// copy rest of the elements from the original array
int i = steps;
for(int j = 0; j < numArr.length - steps; j++, i++){
temp[i] = numArr[j];
}
System.out.println("Array after right rotation- " + Arrays.toString(temp));
}
}
Output
Array after right rotation- [6, 7, 8, 1, 2, 3, 4, 5]
Time and space complexity
With this approach you need a temporary array of size n (same size as original array) so the space complexity is O(n).
Time Complexity is sum of the following actions
- Creating the temporary array: O(n), where n is the size of the original array.
- Copying elements into the temporary array: O(n).
- Copying back into the original array using System.arraycopy(): O(n).
Thus the overall time complexity is O(n).
Array rotation program- using loops
This Java program for array rotation uses inner and outer for loops for shifting and copying elements.
Solution using loops works as follows-- In an outer loop, copy the first element (in case of left rotation) or last element (in case of right rotation) in a temporary variable.
- Shift elements to the left or right as per rotation requirement in an inner loop one step at a time.
- Once out of inner loop copy the element stored in temp variable to its final position.
- Repeat the process for the total rotation steps.
public class ArrayRotation {
public static void main(String[] args) {
int[] numArr={1,2,3,4,5,6,7,8};
rotateLeft(numArr, 2);
//rotateRight(numArr, 3);
}
private static void rotateLeft(int[] numArr, int steps){
for(int i = 0; i < steps; i++){
// store the first element
int temp = numArr[0];
for(int j = 0; j < numArr.length - 1; j++){
// shift element to the left by 1 position
numArr[j] = numArr[j + 1];
}
// copy stored element to the last
numArr[numArr.length - 1] = temp;
}
System.out.println("Array after left rotation- " + Arrays.toString(numArr));
}
private static void rotateRight(int[] numArr, int steps){
for(int i = 0; i < steps; i++){
int temp = numArr[numArr.length-1];
for(int j = numArr.length-1; j > 0; j--){
numArr[j] = numArr[j -1];
}
// copy stored element to the beginning
numArr[0] = temp;
}
System.out.println("Array after right rotation- " + Arrays.toString(numArr));
}
}
Output
Array after left rotation- [3, 4, 5, 6, 7, 8, 1, 2]
Time and space complexity
With this approach, if you need to rotate by n steps, and the array length is m, each step requires O(m) operations. So, the total number of operations = n * m. Thus the time complexity is O(n*m).
There is no extra space requirement so the space Complexity is O(1).
That's all for this topic Array Rotation Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-