In this post, we will see how to reverse an array in Java.
1. Naive
Simple solution is to create a new array of same type and size as the input array, fill it with elements from original array in reverse order, and then copy contents of the new array into the original one.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
import java.util.Arrays; class Reverse { // Utility function to reverse elements of an array public static void reverse(int[] A) { int[] B = new int[A.length]; for (int i = 0; i < A.length; i++) { B[A.length - 1 - i] = A[i]; } for (int i = 0; i < A.length; i++) { A[i] = B[i]; } } public static void main(String[] args) { int[] A = { 1, 2, 3, 4, 5 }; reverse(A); System.out.println(Arrays.toString(A)); } } |
2. In-place implementation
Above implementation requires O(n) extra space for the auxiliary array. We can avoid that by modifying the array in-place. That means that the conversion should take place without using an auxiliary array, by overwriting the existing elements of the array.
An in-place algorithm can be implemented by reading the elements from both ends of the array and swap them as shown below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
import java.util.Arrays; class Reverse { // Utility function to swap two elements A[i] and A[j] in the array private static void swap(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } // Utility function to reverse elements of an array public static void reverse(int[] A) { for (int low = 0, high = A.length - 1; low < high; low++, high--) { swap(A, low, high); } } public static void main(String[] args) { int[] A = { 1, 2, 3, 4, 5 }; reverse(A); System.out.println(Arrays.toString(A)); } } |
We can also use recursion for reversing an array without using an auxiliary array. The logic remains same as the above iterative implementation but it takes space for the call stack.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import java.util.Arrays; class Reverse { // Utility function to swap two elements A[i] and A[j] in the array private static void swap(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } // Recursive function to reverse elements of a sub-array formed // by A[low, high] public static void reverse(int[] A, int low, int high) { if (low < high) { swap(A, low, high); reverse(A, low + 1, high - 1); } } // Utility function to reverse elements of an array public static void reverse(int[] A) { reverse(A, 0, A.length-1); } public static void main(String[] args) { int[] A = { 1, 2, 3, 4, 5 }; reverse(A); System.out.println(Arrays.toString(A)); } } |
3. Using Stack (Implicit and Explicit stack)
Another plausible way of reversing an array is to use the stack data structure. The idea is to push each element in the array into a stack. Then we simply pop values from the stack one by one and assign each popped item back to the original array starting from the beginning.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.Arrays; import java.util.Stack; class Reverse { // Utility function to reverse elements of an array public static void reverse(int[] A) { // create an empty stack of integers Stack<Integer> stack = new Stack<>(); // push each element in the array into a stack for (int i: A) { stack.push(i); } // start from index 0 int index = 0; // pop values from the stack until it is empty while (!stack.isEmpty()) { // assign each popped item back to the original array A[index++] = stack.pop(); } } public static void main(String[] args) { int[] A = { 1, 2, 3, 4, 5 }; reverse(A); System.out.println(Arrays.toString(A)); } } |
We can easily convert above code to use recursion call stack instead of explicit stack. Here’s a recursive program that demonstrates it:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.Arrays; class Reverse { // Utility function to reverse elements of an array public static void reverse(int[] A, int nextIndex) { // base case: empty array or end of array is reached if (A == null || nextIndex == A.length) return; // store next element of the array int value = A[nextIndex]; // reach end of the array using recursion reverse(A, nextIndex + 1); // put elements in the call stack back into the array // starting from the beginning A[A.length - nextIndex - 1] = value; } public static void main(String[] args) { int[] A = { 1, 2, 3, 4, 5 }; reverse(A, 0); System.out.println(Arrays.toString(A)); } } |
4. Collections#reverse method
Finally, reverse() method of the Collections class can be used to reverse the order of the elements in the specified array. Since it accepts a collection as argument, the idea is to pass a list wrapper which is backed by the given array.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
import java.util.Arrays; import java.util.Collections; class Reverse { public static void main(String[] args) { Integer[] A = { 1, 2, 3, 4, 5 }; Collections.reverse(Arrays.asList(A)); System.out.println(Arrays.toString(A)); } } |
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply