Write a program to reverse an array
You are given an array, and you will have to reverse the array elements. Pretty simple right? Well the brute force approach that comes to your mind is that let's just take another empty array of the size the same as the length of the original array and then iterate through the original array in reverse and keep storing the array elements from the original array and keep putting it in the new array from the starting index of It. at the end you can again copy all the elements from the new array to our original array that overrides the previously present in it and ultimately gives us back our desired output.
Here's the code to the brute force approach.
Code:
class ArrayReverse {
public static void main(String[] args) {
int arr[] = { 1, 9, 2, 3, 4, 7 };
//function to reverse the array
reverse(arr);
// printing the output
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
static void reverse(int arr[]) {
int[] a = new int[arr.length];
int index = 0;
// iterating arr in reverse
for (int i = arr.length - 1; i >= 0; i--) {
// adding elements from the original array to the new array
a[index++] = arr[i];
}
// puttting it back in the original array
for (int i = 0; i < arr.length; i++) {
arr[i] = a[i];
}
}
}
How it should be done:
The above solution is ok but has some tiny issues. First, as you can see for such a simple problem we had to write so much code. Secondly, although our solution is taking O(n) times, we are using an auxiliary array of size N( the size of our original array). it's ok for our small test case but what if N is a whole big of a number, say in millions. Then it's going to cost us memory. So let's see the best solution.
Here we are kind of using two pointer approach. We will be iterating through the array, but till the middle index(N/2) I'll come to the why part later. Then without using any extra array, we will be using our original array and we will swap elements at the ith index with the element at the N-ith-1 index. Let me elaborate, let's say our N or size of the array is 6, suppose we want to put the element at the 0th index in its correct place in the reversed array, it should be at the last index i.e, 5th index and how can we get that, using a simple formula N-i-1 (6-0-1). same for other indexes if i=1 then it should go at 4th index, n-i-1 / 6-1-1 = 4. So in simple words, if we want to find out for any given index of i we would be able to calculate the index where the ith element must be placed using the formula N-i-1 and then we swap the elements at both of the indexes.
Now if you clearly do a dry run of the algorithm you will see that in every iteration we are putting two elements at it's correct place in the reversed array. So in the first iteration two elements are at their correct place, in 2nd iteration four elements are at their correct place and in the 3rd iteration six elements are in the correct place. So if you array is of size 6 we need only three iterations to get to the answer or N/2 i.e, 6/2=3. So now you know why we are iterating till N/2. This also reduces the time complexity of our program.
Code:
class ArrayReverse {
public static void main(String[] args) {
int[] arr = { 1, 6, 5, 4, 2, 3 };// given array
int n = arr.length; // length
for (int i = 0; i < n / 2; i++) {
// swap
int temp = arr[i];
arr[i] = arr[n - i - 1];
arr[n - i - 1] = temp;
}
// output
for (int i : arr) {
System.out.print(i + " ");
}
}
}
As you can see how our optimized solution has reduced the code and we are not even using any extra space and even better our algorithm takes less time to run.
Hope the explanation was easy to understand for you, I have tried to keep it short and simple. Still if you are stuck at any point you can reach out to me through my socials I will be more than happy to help you and in the mean time you can also watch my video on this topic as well.
Hope you had a good time today and I'll be glad to know if this article was of any help to you, dropping my social handles and looking forward to hear from you. Thank you and have a nice day.