Array — 1. Reverse An Array
In many blog posts about Data Structures and Algorithms, people just give the solution directly without explaining the thought process on how they got to the solution. So in this post I will try to explain the same.
Question
Reverse a given array / string without using built-in functions
Examples
Input : [1, 2, 3, 4]
Output : [4, 3, 2, 1]
Brute Force Solution (Naïve)
Create a new array in which we will store the required output.
We will start traversing the original array from the last position to the first position
[1, 2, 3, 4]
^
Add 4 to the new array --> [4][1, 2, 3, 4]
^
Add 3 to the new array --> [4, 3][1, 2, 3, 4]
^
Add 2 to the new array --> [4, 3, 2][1, 2, 3, 4]
^
Add 1 to the new array --> [4, 3, 2, 1]
Code
Space / Time Complexity — Brute Force
Let n be the size of the given input array
Space Complexity → O(n)
We created a new array to store the elements of the original one.
Time Complexity → O(n)
Iterating through each element only once
Bottlenecks / Unnecessary Work / Duplicate Work (BUD)
Well, the time complexity cannot be improved.
For space complexity, can it be done in CONSTANT SPACE ?
For constant space, it means that we have to make changes in-place (that is without creating a new array).
Tips / Hints
Usually, in array questions most of them can be solved using 2 pointers. So try to optimize it using 2 pointers.
Optimize
To make changes in the same array, we need to swap numbers in such a way,
that the last item becomes the 1st item, 1st item becomes the last item,
2nd Last item becomes 2nd and 2nd item becomes 2nd last.
So on and so forth…
For this we require 2 pointers.
One at the end. and One at the start.
1 2 3 4^ ^l rSWAP THEM4 2 3 1^ ^l rSWAP THEM4 3 2 1^ ^r lSTOP
Space / Time Complexity — Optimal Solution
Let n be the size of the given input array
Space Complexity → O(1)
We do not create a new array. All changes occur in the same array
Time Complexity → O(n)
Iterating through each element only once
Implementation of Optimal Solution
Test Border Case Scenarios
Does it work when array = [] (empty)
Yes. Left = 0, Right = -1. Right < Left. Loop will not execute.
What if we pass anything other than array / string?
Can check the type of the arguments/elements.
Comment below if you have any doubts / suggestions.
😃
