Hi everyone, I hope you have given it a shot.
Now let's code together the solution that we discussed in the previous video.
Now for this, let's start by creating a function and let's call this function find indices some given.
And as mentioned in the question, we pass the array and the target value into this function.
Now we are going to initialize a hash table.
That's how we are going to avoid the need for two for loops, which was costing us a lot of complexity
which was increasing increasing the time complexity.
So let's call this hash table itself.
And initially this hash table is empty.
Now we need to traverse the array once.
For this we will use a for loop.
But before that let me just create a variable needed value.
We will use this to check whether the needed value is already there in the hash table.
Now for traversing the array once we are using the for loop.
So let's write for.
Let I is equal to zero I less than.
Array dot length.
Because we need to go through the complete array.
Right.
So we are doing it up to I less than array dot length and I plus plus.
Now inside the for loop.
First let's calculate the needed value.
Now again over here.
Let me just show what's happening.
Let's take an example.
Let's say the given array is again 123.
And let's say the target value is three.
Or let's take another example.
Let's say 1234.
And let's say the target value is um seven.
So let me write that.
So target value is equal to seven.
To make the logic clear.
Now we are inside the for loop and I is equal to zero at this point.
Now in the zeroth index the value in the given array is equal to one.
Now we are going to calculate the needed value at this point.
So the needed value is nothing but the target value minus the value that we have.
Right.
So needed value is equal to.
Target value.
Minus array at I.
Okay.
So in this case we have an array at I is one and the needed value.
Let me write that as n v needed value is equal to seven minus one which is equal to six.
Now we are going to check whether this six already occurred before.
Now we are starting with this iteration.
So yes it does not make sense because it's going to be empty anyway.
The hash table is empty.
But going forward this is what we will be repeatedly doing in each iteration.
So let's do that over here.
We're going to check whether the needed value is in the hash table.
So if needed value in hash table.
So if it is there it means that it already occurred in the array before.
Right.
So we have found the answer.
Now if it is there we are going to return.
The indices, the required indices.
Now in this case the one index is I because we are at the I th value right and the other index will
be stored as the value when we pass the needed value as a key in the hash table.
All right.
So let's just hold this for a minute and let's write the else part and come back so that it will be
clear because we have not yet written what comes into the hash table.
Right.
So let me just leave that for a moment and write the else part.
So if the needed value is not there in the hash table, what do we do?
We insert the value.
We insert a of I into the hash table.
So let's write that hash table.
At a of I.
So the key is array of I.
The key is the array of the value.
In this case the key is one.
So 1234.
These are going to be the keys in the hash table.
And the value will be the index.
Because we need to return the index at the end of the day.
Right.
So we need to be able to read the index from the hash table.
That's why we are storing the value as the index.
And the key is the value of the array.
So in this case we are going to store in the hash table.
Let me write that also over here.
So in the first iteration when RA of I is equal to one we are in the hash table.
Initially the hash table is empty.
Now at this point we are going to see that the required value needed value, which is six, is not there
in the hash table.
So let's store one in the hash table.
And we also need to store the index of one.
So we are going to store one and zero.
So one is the value.
This one over here.
And zero is the index.
This is at the zeroth index.
All right.
So we're going to keep doing this now in the next iteration.
So over here you can see if needed value.
So let's just complete this part which we left for a moment.
So when the needed value is in the hash table that means let's say over here we are at uh for let's
say we have traversed till four.
Now let me just write that over here.
What would be the hash table at that point?
It would be two one and three two.
Right.
And then we are at four.
So array of I is four.
Now at that point the needed value will be equal to.
Four seven minus four, which is equal to three.
Right.
And we will see that it's already there in the hash table.
It's there.
Right.
So we know that it already occurred.
So that's the case which we are writing over here.
At this point we need to return the indices.
So one index will be I which is the index of four in this at this point.
And the other case would be the value at the uh key of three in the hash table.
Right.
So we need to take the value by passing in the key.
So let's do that hash table.
And we are going to pass in the value as needed value.
So we are going to return this at this point.
And there we have our solution.
Now the only thing that remains is if we come out of this for loop without returning anything, that
means we were not able to find a pair that adds up to the target value, and we will return the empty
array.
And there we have our solution.
Now let's go ahead and test whether our solution is working for this.
Let me say array is equal to for example one minus two 345.
And let's say target value.
Is equal to, let's say three.
Okay.
Now let's console log what we get when we call our function.
So we have find indices some given.
And we are passing the array and the target value.
Now let's see what happens.
So I'm running this.
Now when we run this, you can see that we get the array four comma one as output.
So index four is 01234 which is five.
So value five is at index four.
And at index one we have minus two right 015 plus minus two gives us three.
So yes our algorithm is working.
Now what if I pass an empty array.
And let's run it.
So I get an empty array as output so it works.
If it's a single element array, again I get an empty array which works.
And let's say I have three comma nine and the target value is also 12.
If I run it, I'll get the answer as one comma two.
So yes, our algorithm is working.
Now let's take a relook at the code that we have written to analyze in greater depth what is happening.