Hi everyone.
So we have discussed the brute force solution for this question.
Now let's try to see how we can solve this question in a more optimal manner.
Now over here we have seen that for each value of I we were traversing the array again and again.
Right.
So we are not storing the values anywhere.
The same value which was accessed over here is again accessed over here by traversing the array.
Right.
So this is not an efficient way of solving it.
And because of that we got a time complexity of O of N square.
Right.
Now let's try to avoid this scenario where at each I we were traversing the array again and again.
So for each of these N operations we were doing n operations again.
Right.
So that's why the time complexity was O of n square.
And the basic reason for this was we were not storing anything.
So let's try to store.
So we are using some space but we will try to optimize the time complexity.
All right.
So let's try to do that.
So we have a sample input.
So let's take this as the input array.
And the target value is equal to two.
Now we will try to make use of a hash table to solve this.
And the property of a hash table which we are using over here is that lookup.
When we try to look up a value from a hash table, when we have the key is a constant time operation
or a O of one operation.
So this is the concept that we are going to use over here.
And we have seen that in the previous method we were not storing anything.
Now what we are going to do over here is as we traverse the array, we will keep storing the values
in the hash table so that later, when we want to see whether a particular value is there in the array
or not.
And when that value is something that we have already traversed, we don't need to traverse the array
again, but rather we will just access it from the hash table.
We will just check it from the hash table.
And we don't need to traverse the array again.
So that's the basic thing that we are trying to implement.
All right.
So let's make some space over here.
Now we will have a pointer.
Yes definitely.
We'll have to traverse the array once.
So let the pointer initially point to index zero which has value two.
And let's make a hash table.
Initially the hash table is empty.
All right.
Now we will check what value we need along with two to get to the target value which is also two right.
So this two plus something is equal to the target value which is two.
So the needed value at this point is two minus two which is equal to zero.
Right.
Because two plus zero is equal to two.
Now we will check whether this zero is there in the hash table.
And because again we are starting the algorithm.
So at this point it is not there.
So if it is not there in this case zero is not there in the hash table.
What we will do is we will insert this value into the hash table.
So we will insert two into our hash table.
Now let me do that.
And again because the question says that at the end we need to return the indices of the values which
add up to the target value.
So when we insert two in the hash table, two is going to be the key and the value is going to be the
index.
So at this point we are going to insert into the hash table two zero.
This two is this value.
And this zero over here is this index.
So the pair the key value pair that we're inserting over here is two zero.
So notice what we're doing over here.
We are storing the array into the hash table.
Right.
So we don't need to traverse the array again to see whether we have two or not in the array.
So that's the basic thing that we're trying to do over here.
All right.
Now again we move the pointer from two to the next index which is seven.
Now what is the needed value at this point seven plus something is equal to two.
So the needed value is two minus seven which is equal to minus five.
So we are going to check whether minus five is already there in the array.
And for that we are not going to traverse the array.
But rather we will just check whether minus five is in the hash table or not.
Right.
So at this point minus five is not there in the hash table.
Right?
It's not there in the hash table.
So what do we do.
We insert this seven into the hash table.
So that's what you're going to do.
We're inserting the array elements into the hash table.
So let's insert seven and one.
So this seven is the value of the array right.
This is the key of the hash table.
But that's the value which you have in the array.
And over here this one is this index.
All right.
Now let's make some space.
We move the pointer from 7 to 3 okay.
So again three plus something is equal to two.
So we need minus one.
We are going to check whether minus one is in this array.
Not by traversing the array but by checking whether it's there in the hash table.
All right.
Now you can see that minus one is not in the hash table right.
Minus one is not in the hash table.
So what do we do.
We insert this three into the hash table.
So that's 323 is this value.
And two is the index which is this one over here.
So we insert three and two into the hash table.
Now we again move the pointer and we have minus one.
So minus one plus something is equal to two.
So the needed value in this point is two minus minus one which is equal to three.
And we are going to check whether three is already there in the array.
Not by traversing the array but by checking the hash table.
And when we do that we can see yes, three is already there in the hash table, which means that three
is there previously in the array.
Right.
So yes we have found our solution.
Right.
This means three is there in the array.
So we have the answer.
And remember we need to return the indices.
So the index of value three in the array is this two over here.
So we are going to return this two and this index over here already we have the pointer which is pointing
to index three.
Right.
So we are going to return these two indices this two and this three.
That's two comma three which is our answer.
Now again quickly let's revise what we did.
Basically we are ensuring that we need to traverse the array only once.
And if when we whenever we encounter an element of the array, we check whether the needed value is
already there in the array because it's a pair, right?
We need two values.
For example two we needed zero for seven, we needed five for three, we needed minus one, etc. so
when we were at the index which had the value two, we are checking whether zero is already there in
the array, not by traversing the array, but by checking the hash table.
Similarly, when we were at the index which had the value seven, this one over here, we were checking
whether five is already there in the array by checking whether it's there in the hash table, and if
it's not, we were inserting right.
So at this point we inserted two zero.
Then we inserted seven one.
At this point we inserted three two.
And when we reached over here we checked whether we have three in the array in the previous elements
of the array which were already traversed not by again traversing the array, but by checking the hash
table.
And we saw it's there right.
So we got the answer.
And the answer is minus one and three.
These add up to two.
And we return the indices because we are storing the index over here we got the index of three from
the hash table and the index of minus one.
We got it because that's that was stored in the pointer right.
So we returned two comma three which is the answer.
Now let's look at the space and time complexity of this solution.
Right.
So the time complexity of this solution is O of n.
We have seen that the time complexity of the brute force solution where we had two for loops.
Right.
So there was a nested for loop.
The time complexity was O of n square.
So we were able to improve upon that to O of n.
Why is that.
So we are traversing the array only once, right?
We are traversing it only once, which is what we have done, which is what we are doing over here.
And remember accessing from the hash table when we know the key is a constant time operation.
So checking whether it's in it's a particular value is in the hash table.
And if it's there taking the index is a constant time operation.
So that's not adding to our time complexity.
So the time complexity over here is O of N.
And the space complexity over here is also O of n.
Right.
Because max we need to insert n pairs into the hash table.
Right.
Let's say we have these five elements.
So in the worst case our hash table will have five pairs right 207132 minus one and three and four comma
four.
Right.
So that's the worst case scenario.
And this is n elements.
So if there are n elements in the input array the hash table will have at the most n pairs.
So that's why because we are storing this extra hash table.
That's why the space complexity of the solution is O of n.
So in the brute force solution the space complexity was O of one.
But by increasing the space used to O of N, we were able to improve the time complexity in the brute
force solution.
It was O of n square, but we were able to improve it to O of n.