It's relatively 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 and other beginner Programmers. But, don't worry, I'll tell you how you can solve this problem without losing your cool. 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 or in-place as described in many Algorithms books and courses, and on Coding interviews.
All you need to do is a loop over the array from start to the middle element and swap the first element to the last, second element to the second last until you reach the middle element. Once you reach the middle element, your array is already sorted, and that too without using any additional space or in-place as asked in this question.
You can even use this algorithm to reverse a String in Java as well. After all, a String is backed by a character array in Java and other programming languages like C and C++. This is as simple as it could be, but you know, this is also the fastest way to reverse an array in Java.
In general, Data structure and Algorithm questions like ones based upon the array, linked list, binary tree, hash table, and searching/sorting algorithms are very important for programming job interviews and you should have a good knowledge of them.
If you feel that your data structure and algorithm skills are lacking or you want to learn them from scratch, I suggest you join a comprehensive course like Data Structures and Algorithms: Deep Dive Using Java on Udemy, which will teach you all of these and much more useful stuff on Algorithms. It's one of my favorite courses on this topic.
So, let's see 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 loops over the array and swaps elements like starting from the first element, it swaps the first to last, second to the second last, until it reaches the middle of the array.
At this 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 the same space.
Obviously, all-in-place algorithms have constant space complexity. Btw, if you have trouble understanding Big O notation and how to calculate the time and space complexity of any arbitrary algorithm then I suggest you check out Algorithms and Data Structures - Part 1 and 2 courses on Pluralsight, which will teach you the technique of calculating these numbers.
This is also the fastest way to reverse an array in Java. It cannot be faster than this because we are only accessing an array which is a 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:
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 like reversing an array of the even number of elements, but I expect it to work.
Please drop a note, 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 the 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:
P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free Data STructure and Algorithms courses from Coursera and Udemy. It's completely free of cost.
All you need to do is a loop over the array from start to the middle element and swap the first element to the last, second element to the second last until you reach the middle element. Once you reach the middle element, your array is already sorted, and that too without using any additional space or in-place as asked in this question.
You can even use this algorithm to reverse a String in Java as well. After all, a String is backed by a character array in Java and other programming languages like C and C++. This is as simple as it could be, but you know, this is also the fastest way to reverse an array in Java.
In general, Data structure and Algorithm questions like ones based upon the array, linked list, binary tree, hash table, and searching/sorting algorithms are very important for programming job interviews and you should have a good knowledge of them.
If you feel that your data structure and algorithm skills are lacking or you want to learn them from scratch, I suggest you join a comprehensive course like Data Structures and Algorithms: Deep Dive Using Java on Udemy, which will teach you all of these and much more useful stuff on Algorithms. It's one of my favorite courses on this topic.
How to Reverse an array in-place in Java
In the last section, I have explained to you the logic or algorithm to reverse an array in place, now is the time to convert that algorithm into pseudo-code and then real code in Java. You will also calculate the time and space complexity of our solution, which is often required in Interviews as well as in the real world to meet your performance SLA.So, let's see 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 loops over the array and swaps elements like starting from the first element, it swaps the first to last, second to the second last, until it reaches the middle of the array.
At this 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 the same space.
Obviously, all-in-place algorithms have constant space complexity. Btw, if you have trouble understanding Big O notation and how to calculate the time and space complexity of any arbitrary algorithm then I suggest you check out Algorithms and Data Structures - Part 1 and 2 courses on Pluralsight, which will teach you the technique of calculating these numbers.
Java Program to Reverse an array of String in place
Here is our Java program which implements this algorithm to sort a string array. You can use this algorithm to sort any kind of array like a boolean array, int array, String array, or any custom object array.This is also the fastest way to reverse an array in Java. It cannot be faster than this because we are only accessing an array which is a 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:
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 like reversing an array of the even number of elements, but I expect it to work.
Please drop a note, 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 the 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)
- 20+ array-based coding problems for programmers (questions)
- How to remove an element from an array in Java? (solution)
- 7 Best Courses to learn Data Structure and Algorithms (courses)
- How to check if an array contains a particular value? (solution)
- How to find duplicates from an unsorted array in Java? (solution)
- 7 Free Books to learn Data Structure and Algorithms (books)
- How to find one missing number in a sorted array? (solution)
- How to find all pairs in an array whose sum is equal to k (solution)
- How to remove duplicates from an array in Java? (solution)
- How to find a missing value from an array containing 1 to 100? (solution)
- 50+ Data Structure and Algorithms Problems from Interviews (questions)
- My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
- Iterative PreOrder traversal in a binary tree (solution)
- How to count the number of leaf nodes in a given binary tree in Java? (solution)
- Recursive InOrder traversal Algorithm (solution)
- 10 Free Data Structure and Algorithm Courses for Programmers (courses)
- 100+ Data Structure Coding Problems from Interviews (questions)
P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free Data STructure and Algorithms courses from Coursera and Udemy. It's completely free of cost.
ReplyDeletepackage com.test.integer;
import java.util.Arrays;
public class ReverseArrayInPlace {
public static void main(String[] args) {
int[] intArr = {1,2,3,4,5,6};
int length = intArr.length;
for(int i=0; i < length/2; i++){
int temp = intArr[i];
intArr[i] = intArr[(length-1)-i];
intArr[(length-1)-i] = temp;
}
System.out.println(Arrays.toString(intArr));
}
}
Why is it length/2 ?
Deleteit is enough to iterate for half length.here length is 6,so length/2=3
DeleteYes, because you are swapping elements, you are arranging two elements in one go, hence, to arrange all elements, you just need to it for length/2
DeleteWhy do you say it is O(n)? You are iterating only half of the array, so it is O(n/2). Isn't it?
Deletepublic static String[] reverseStringField(String[] arr){
ReplyDeleteString[] reverseArr= new String[arr.length];
int j =0;
for (int i = arr.length-1; i >=0; i--) {
reverseArr[j] =arr[i] ;
j++;
}
return reverseArr;
}