Implementing Array Reversal Algorithm Using Java

Array Reversal means reversing the order of elements inside an array. An Array Reversal Algorithm should strive to perform the reversal in the least amount of time complexity and space complexity.

In this post, we will look at couple of algorithms for array reversal. Then, we will implement the best of the two Array Reversal Algorithm in Java.

Problem Statement

Consider an array of N elements. The problem is to reverse the array. This means reversing the order of the elements inside the array.

For example:

Input : array[] = {1, 2, 3}

Output : array[] = {3, 2, 1}

Another example:

Input : array[] = {4, 5, 3, 8}

Output : array[] = {8, 3, 5, 4}

The Solution

There are a couple of Array Reversal Algorithms that can be used to solve this problem.

Approach 1 – Using Temporary Array

This is by far the most common approach to reverse an array. In this approach, you basically copy all the elements of an array into a temporary array.

Then, you traverse through the temporary array from the end and replace the elements in the original array one by one.

As you can see, this Array Reversal Algorithm involves two loops that iterate through all the elements of the array. Therefore the time complexity of this algorithm is O(n). However, this approach also uses extra space because of the temporary array.

Approach 2 – Reversing in position

This method is much better because it avoids using extra space. The idea behind this approach is to traverse the array from both ends and keep swapping the elements until we reach the middle of the array.

Let’s understand the approach using pseudo-code:

• Initialize start and end index as follows
  • start = 0 & end = N – 1 (where N is the number of elements in the array)
• In a loop do the following
  • swap array[start] with array[end]
  • start = start + 1
  • end = end – 1

In this approach, even though the time complexity is still O(n) but space complexity is much less. The advantages become much clearer for large arrays.

Implementation

Now, let’s see the implementation for Approach 2 using java. We can do it in two ways

Normal Method

Below is the code for the normal method using Approach 2.

public static int[] reverseArray(int[] array){
        int start = 0;
        int end = array.length - 1;

        while (start < end){
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
        return array;
}

Recursive Method

The same problem can also be solved using recursion. To do so, the only difference is defining a method that also takes the start and end indexes so that it can be called recursively.

public static void recursiveArrayReversal(int[] array, int start, int end){

        if (start >= end)
            return;

        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;

        recursiveArrayReversal(array, start+1, end-1);
}

The Driver Method

Below is the driver method to test both of the approaches i.e. the normal one and the recursive one.

public static void main(String[] args) {

        int[] array = {1, 2, 3, 4, 5};
        System.out.println(Arrays.toString(reverseArray(array)));

        int[] anotherArray = {1, 2, 3, 4, 5};
        recursiveArrayReversal(anotherArray, 0, anotherArray.length-1);
        System.out.println(Arrays.toString(anotherArray));

}

Conclusion

In this post, we understood the concept behind array reversal and couple of approaches to do the same.

Then, we successfully implemented Array Reversal Algorithm using in-position swap since it does not cause wastage of space. We also used a normal approach as well as the recursive approach.

That was all about array reversal. Hope this post was useful.

Happy learning!