Java Program to reverse an array in place? Fastest Example

It's easy to reverse an array if you have the luxury to use another array, but how would you reverse an array if a temporary buffer is not allowed? This is one of the testing array interview questions, which often proved tricky for Java programmers. Well, you can also reverse an array in place without using an additional buffer. If you know how to access array elements and how to loop over an array in Java using traditional for loop, you can easily solve this problem without using additional space. All you need to do is loop over the array from start to the middle element and swap first element to the last, second element to the second last etc. Once you reach the middle element, your array is already sorted and that too without using any additional space. You can even use this algorithm to reverse a String in Java as well. After all, a String is backed by character array.

This is as simple as it could be, but you know, this is also the fastest way to reverse an array in Java. Data structure and algorithm questions are very important for programming job interviews and if you are preparing for one then don't forget to check out Cracking the Coding Interview book, It contains over 150 programming questions and solutions for good preparation.



How to reverse an array in-place in Java

Here is an example of how you can reverse an array of String in Java in place. This program doesn't use a temporary buffer or another array, instead, it just loop over array and swap elements e.g. starting from the first element, it swap the first to last, second to the second last, until it reaches the middle of the array. At that point all elements are already swapped, so your array is fully reversed.

This is a simple algorithm and time complexity is O(n/2) or O(n) because it needs to iterate over almost half the elements and perform n/2 swapping as well. The space complexity of the algorithm is O(1) because no matter how big the array is, it requires same space. Obviously, all in place algorithms has constant space complexity.

This is also the fastest way to reverse an array in Java. It cannot be faster than this because we are only accessing array which is constant time operation. The only thing you can optimize is to minimize swapping. Do you know any other way to make this algorithm faster? If yes, then please let us know.

If you want to solve this problem by using recursion instead of the iterative way (using for loop), you can customize your algorithm like below:

Fastest way to reverse array in place in Java


Java Program to reverse an array of String in place
Here is our Java program which implement this algorithm to sort a String array. You can use this algorithm to sort any kind of array e.g. boolean array, int array, String array or any custom object array.

package coding;

import java.util.Arrays;

/**
 * Java Program to reverse array in place. Time complexity is O(n)
  *You cannot use additional buffer but one or two variables are fine.
 *
 * @author WINDOWS 8
 *
 */
public class ReverseArrayInPlace {
   
    public static void main(String args[]){
       
        String[] names = {"John", "Jammy", "Luke"};
        System.out.println("original array: " + Arrays.toString(names) );
       
        // reversing array with three elements
        reverse(names);
        System.out.println("reversed array: " + Arrays.toString(names) );
       
        String[] test = {"John"};
        System.out.println("original array: " + Arrays.toString(test) );
       
        // testing reverse array function with array of just one element
        reverse(test);
        System.out.println("reversed array: " + Arrays.toString(test) );
    }

    /**
     * Java Method to reverse String array in place
     *
     * @param array
     */
    public static void reverse(String[] array) {

        if (array == null || array.length < 2) {
            return;
        }

        for (int i = 0; i < array.length / 2; i++) {
            String temp = array[i];
            array[i] = array[array.length - 1 - i];
            array[array.length - 1 - i] = temp;
        }

    }

}

Output :
original array: [John, Jammy, Luke]
reversed array: [Luke, Jammy, John]
original array: [John]
reversed array: [John]

You can see from the output that our program is working fine for an odd number of elements. I haven't tested it for all kinds of input e.g. reversing array of the even number of elements, but I expect it to work. Let me know if you find any bug or issue and the program is not working for any input.

That's all about how to reverse an array in place in Java. This is one of the essential coding exercises for Java programmers learning data structure and algorithms. Remember, it's an in-place algorithm hence, the space complexity is O(1) and time complexity of this solution is O(n). This is also the fastest way to reverse the array in Java.

Other array based coding problems for Interviews:
  • How to find the largest and smallest number in an array without sorting? (solution)
  • How to remove an element from an array in Java? (solution)
  • How to check if an array contains a particular value? (solution)
  • How to find duplicates from an unsorted array in Java? (solution)
  • How to find one missing number in  a sorted array? (solution)
  • How to find all pairs in array whose sum is equal to k (solution)
  • How to remove duplicates from an array in Java? (solution)

Further Reading
150 Programming Questions and Solutions
Data Structure and Algorithms in Java


No comments:

Post a Comment