Hi everyone.
So we have coded the optimal solution.
Now let's take a test case and walk through the code that we've written.
For this.
Let's take the RA two minus one five three and let the target value be equal to four.
Now let's write the indices of the given array.
So this is 012 and three.
All right.
Now we are let's say we have called this function.
And we have passed the array two minus one five three.
And we have passed the target value four.
So at this point we will initialize the hash table.
And it's going to be empty at this point.
All right.
Now we have now declared a variable needed value.
And then we enter the for loop.
Now we can see that in this optimal solution we have only one for loop.
So that's the reason why we have been able to optimize the time complexity compared to the brute force
solution.
Now initially the value of I is equal to zero.
So at this point we come inside the for loop and at the i'th index the needed value is calculated right.
So at the ith index.
In this case at the zeroth index the value is two.
It's the value that we have so needed value is equal to target value minus array at I array at I is
equal to two.
So needed value is equal to four minus two.
Right.
So needed value is equal to two.
Now what do we mean with this.
If we have two and if we have another two then we can get to the target value which is four.
So the needed value for two and this one to work is equal to two.
So we have calculated the needle value.
And we are going to check whether the needed value is in the hash table.
Now at this point our hash table is empty so it's not there.
So because it's not there we come to the else part and we insert the value into the hash table.
And what are we inserting.
We are inserting a key value pair in the hash table.
Now the key is array of I.
And the value is the index.
So that's what we're doing over here right.
So at the key array of I which is equal to two.
At this point we are inserting the index which is equal to zero.
So we are inserting the pair two zero.
Now again we increment I by one.
So I is equal to one at this point.
And the needed value is equal to five.
Right.
Because at this at the index one the value which we have is minus one.
So minus one plus something is equal to four which is the target value.
So the needed value this is the needed value is equal to four minus minus one which is equal to five
right.
The needed value at this point is five.
Again we are going to check whether the needed value is in our hash table.
It's not there.
So we insert array of I and the index into our hash table.
So let's do that.
So array of I at this point is minus one and the index is equal to one.
So again you can notice that we are actually inserting the values of the given array into the hash table.
So that we don't need to traverse the array again to access and to check whether the particular value
is there or not in the array.
So that's the aim.
Now again we are incrementing I by one.
And it's still less than array dot length.
Array dot length at this point is equal to four of this array of the given array is four.
So I is equal to two.
Two is less than four.
So we come again inside.
And at this point at the second index the value is five.
Now five plus needed value is equal to four.
So needed value is four minus five which is minus one.
So this is the needed value.
And we check whether the needed value is in the hash table.
And we can see that yes we have the needed value in the hash table.
So we have found the answer.
So this means that if the value in the array at the second index is part of a pair which adds to the
target value, then the other value which is required also has to be there in the hash table.
Right.
So that's what we are checking.
And we found that it is there.
So five will be true if we have minus one.
And we just found that it is there.
So five comma minus one add up to four.
And because we have to return the indices.
So let's take the indices that's two and one.
And we return the indices.
And we have our answer.
Now let me make some space over here.
Now the time complexity of this solution is equal to O of n.
Now why is that so?
Because we have to traverse the array only once.
And we're doing that in this for loop.
Right.
So we are traversing the array only once.
And remember we are accessing values from the hash table.
Now accessing a value from the hash table.
When you know the uh, key that's a constant time operation.
Right.
So that does not add up to our time complexity.
Therefore the time complexity of this algorithm is O of N, and the space complexity is also O of n.
Because we are making this hash table, and this hash table in the worst case will have n key value
pairs, right.
If let's say for each of these we had to insert it.
Then also this hash table will have only n key value pairs.
So the space complexity of this algorithm is O of n.