Tuesday, July 27, 2021

How to Reverse Array in Place in Java? Solution With Explanation

Reversing an array sounds pretty easy, isn't it? It does sound like that, because all you need to do is create an array of the same size, iterate through the original array from end to start, and populate your new array. Boom!!, you have got an array that has elements in reverse order of the original array, but the problem is you have used an additional array here, which makes space complexity of your solution O(n). You cannot use this solution if the array is big e.g. an array of 10 million orders and you don't have enough heap space available.


Can we make it better? Can we reverse an array in Java without using an additional buffer? Even If you encounter this question in your programming job interview, you will be surely asked to reverse the array in place, without using an additional buffer as an earlier solution takes a lot of space. So now your task is to write a Java program to reverse an array in place.

For the sake of this problem, you can assume that it's an integer array (during the interview, you should ask these questions to your interviewer, because asking the right question to fill the gap in requirement is a trait of a good programmer and highly appreciated on both telephonic and face-to-face interviews).

The key point to understand here is that you need to reverse the same array, you cannot use another array but one or two variables is fine. You are also not allowed to use any open source library or Java API which can reverse the array directly like any method from java.util.Arrays class except Arrays.toString()to print arrays in Java. So now the requirement is clear, what approach comes to your mind? how do you solve this problem?





Java Program to Reverse Array In Place - Example

The first thing which comes to my mind is to loop through the array and swap the elements of the array e.g. swap the first element with the last element, swap the second element with the second last element until you reach the middle of the array. This way, all elements of the array will be reversed without using any additional buffer. 

The key thing to keep in mind in this algorithm is that you only need to iterate till the middle element, if you go beyond that then you end up swapping elements twice and result in the same array. Some of you will be puzzled, what is the length of the array is even? 

In that case, there will be two middle elements and we need to swap them, that's why your loop condition should be index <= middle and not index < middle. Here middle index is nothing but length/2

Remember, we are using the division operator, which means if the length is 8 then it will return 4 and when the length is 7 it will return 3. So in the case of even length, the middle element will be swapped twice, but in the case of odd length there is just one middle element and it will not be swapped.

It's been said time and again that a picture is worth a thousand words and true to the point, this image explains the algorithm we used to reverse an array in place quite well. You can see that how elements of arrays are swapped position with each other and middle element remain unchanged, with just two swapping we have reversed an array of five elements.

Algorithm to reverse array in place in Java

Here is our sample Java program to reverse an array in place, solution is simple and easy to follow, but don't forget to look at my JUnit tests to understand it a bit more.

import java.util.Arrays;

/**
 * Java Program to demonstrate how to reverse an array in place.
 */
public class ArrayReversalDemo {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5, 6, 7};
        reverse(numbers);
    }

    /**
     * reverse the given array in place 
     * @param input
     */
    public static void reverse(int[] input) {
        System.out.println("original array : " + Arrays.toString(input));
        
        // handling null, empty and one element array
        if(input == null || input.length <= 1){
            return;
        }       
        
        for (int i = 0; i < input.length / 2; i++) {
            int temp = input[i]; // swap numbers
            input[i] = input[input.length - 1 - i];
            input[input.length - 1 - i] = temp;
        }

        System.out.println("reversed array : " + Arrays.toString(input));
    }
    
    
}

Output
original array : [1, 2, 3, 4, 5, 6, 7]
reversed array : [7, 6, 5, 4, 3, 2, 1]
original array : []
original array : null
original array : [1, 2, 3, 4, 5, 6]
reversed array : [6, 5, 4, 3, 2, 1]
original array : [1]

You can see in output here that input array is reversed properly and in case of null, empty and array with just one element, same array is returned.


JUnit tests

Here is my suite of JUnit tests for our reverse(int[] input)  method. I have made sure to test our solution can handle null, empty array, an array with just one element, and array with even or odd number of elements. You can even test drive this problem. Writing Unit test is a good practice and during Interview, you must write JUnit test even if Interview has not asked for it. This shows that you are a professional software developer and you care for your trade.

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class ArrayReversalDemoTest {
    
    @Test
    public void testReverseWithEvenLengthOfArray(){
        int[] numbers = {1, 2, 3, 4, 5, 6};
        HelloWorld.reverse(numbers);
        assertArrayEquals(new int[]{6, 5, 4, 3, 2, 1}, numbers);
    }
    
    @Test
    public void testReverseWithOddLengthOfArray(){
        int[] numbers = {1, 2, 3, 4, 5, 6, 7};
        HelloWorld.reverse(numbers);
        assertArrayEquals(new int[]{7, 6, 5, 4, 3, 2, 1}, numbers);
    }
    
    @Test
    public void testReverseWithEmptyArray(){
        int[] numbers = {};
        HelloWorld.reverse(numbers);
        assertArrayEquals(new int[]{}, numbers);
    }
    
    @Test
    public void testReverseWithNullArray(){
        int[] numbers = null;
        HelloWorld.reverse(numbers);
        assertArrayEquals(null, numbers);
    }
    
    @Test
    public void testReverseWithJustOneElementArray(){
        int[] numbers = {1};
        HelloWorld.reverse(numbers);
        assertArrayEquals(new int[]{1}, numbers);
    }
   
}

and here is the output of running our unit tests, they all pass.


How to reverse array in place in Java



That's all about how to reverse the array in place in Java. The time complexity of this method is O(n/2) or O(n) because it only iterates through half of the array, but its in O(n) because response time increases in the same order as input increases. As a task, can you find a faster solution of this problem?

By the way, If you like this coding problem and interested for more such problems check out these interesting problems and articles :

  • How to find largest and smallest number in array? (solution)
  • How to find prime factors of an integer in Java? (solution)
  • How to check if LinkedList contains any cycle in Java? (solution)
  • Write a Program remove duplicates from array without using Collection API? (program)
  • How to reverse String in Java without using API methods? (Solution)
  • Write a method to check if two String are Anagram of each other? (method)
  • Write a function to find middle element of linked list in one pass? (solution)
  • How to solve Producer Consumer Problem in Java. (solution)
  • Write a program to find first non repeated characters from String in Java? (program)
  • How to check if a number is binary in Java? (answer)
  • Write a Program to Check if a number is Power of Two or not? (program)
  • Write a program to check if a number is Prime or not? (solution)
  • Write a method to count occurrences of  a character in String? (Solution)
  • How to find Fibonacci sequence upto a given Number? (solution)
  • How to check if a number is Armstrong number or not? (solution)
  • Write a method to remove duplicates from ArrayList in Java? (Solution)
  • Write a program to check if a number is Palindrome or not? (program)
  • Write a program to check if Array contains duplicate number or not? (Solution)
  • How to calculate Sum of Digits of a number in Java? (Solution)
  • How to prevent Deadlock in Java? (solution)
  • How to find largest prime factor of a number in Java? (solution)
  • How to calculate factorial using recursion in Java? (algorithm)
  • How to declare and initialize two dimensional array in Java? (solution)
  • Write a program to find missing number in a sorted array? (algorithm)
  • How to search element in array in Java? (solution)
  • 10 Points about Array in Java? (must know facts)
  • How to find top two maximum on integer array in Java? (solution)
  • How to sort array using bubble sort algorithm? (algorithm)
Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any question or doubt then please let us know and I'll try to find an answer for you.

4 comments :

Unknown said...

This code isn't the best

javin paul said...

@Khai, would have been better if you have put a reason and what you think a better code would be.

SARAL SAXENA said...

@Javin ..just to add with another view point
With Commons.Lang, you could simply use

ArrayUtils.reverse(int[] array)
Most of the time, it's quicker and more bug-safe to stick with easily available libraries already unit-tested and user-tested when they take care of your problem....



If working with data that is more primitive (i.e. char, byte, int, etc) then you can do some fun XOR operations.

public static void reverseArray4(int[] array) {
int len = array.length;
for (int i = 0; i < len/2; i++) {
array[i] = array[i] ^ array[len - i - 1];
array[len - i - 1] = array[i] ^ array[len - i - 1];
array[i] = array[i] ^ array[len - i - 1];
}
}

Anonymous said...

How to reverse a String array in Java? Can you also explain how do calculate time and space complexity of solution?

Post a Comment