Hi everyone.
So we have understood the question and we have formulated test cases.
Now let's try to look at the logic or the method by which we can solve this.
Now the first method that we discussed over here is the brute force method, which is very simple to
understand, but probably not the best or the most optimal solution.
Now let's walk through this.
First.
Let's say the given array is 273 minus one four and the target value is equal to two.
All right.
Now let me write the indices of the elements of the given array.
So 0123 and four.
Now initially we initialize.
Let's say we initialize a pointer and let it point to the first element in the given array.
Now naturally what is it that we are trying to do?
We are we will be looking at, we will keep this constant, and we will look at all the other values
and see if there are any two values which add up to the target value.
Right.
So that's the brute force method.
We are just uh, looking at how a normal person would just, uh, without any knowledge about complexity
would try to solve this.
So we would traverse the remaining elements over here, and let's say we have another pointer and let
that be called J.
And we will see whether any element at the ith index and the jth index when we add them, whether we
can get the target value.
So we will check if array at ith index plus array at jth index.
So this is i'th index element and this is the element at the jth index if they add up to the target
value.
So that's what you are checking.
So we will see if two plus seven is 2 or 2 plus three is two etc..
So now checking this is the same.
Another way in which some people may write this is we could also check whether j is equal to the target
value minus the value at the ith index.
Again, this is the value at the jth index.
All right.
So these two are just one.
And the same thing.
It's just two ways of checking the same thing.
All right.
So we have our array over here.
Now let's try to see how this spans out.
So first our index or our pointer is pointing at two.
So I is equal to two.
All right.
So the value of I is two.
Now what's the value that we need.
Two plus something is equal to the target value which is two.
So the needed value is this two minus what we have over here.
Right.
So that's target value minus the value at the ith index or two minus two which is equal to zero because
two plus zero is equal to two.
So we need zero right.
So we are going to traverse the remaining elements which are these elements which we have seen over
here.
And we are going to check whether we have zero over here.
So over here we have seven, we have three, we have minus one and we have four.
So in none of these we have zero.
So definitely there is no solution in which this is part of the solution.
So we change the value of I by changing the pointer.
And we point to the next element which is seven.
So the value at the ith index now is seven.
Now seven plus something is equal to the target value which is two.
So the needed value is equal to two minus seven which is equal to minus five.
So we are going to check the remaining values which is this part over here.
And we will see whether we have minus five in any of these places.
Now notice that we are only checking the remaining values.
We are not checking what came before it.
Right.
We are not checking what is over here now.
Why is that so?
Because if what is over here was a solution, then it's the same.
Writing the solution as two comma 7 or 7 comma two is one and the same.
Right?
So if what came over here was part of the solution, we would have already found it in the previous
iteration.
But because it was not found in the previous iteration.
So we don't need to check this in the next iteration.
So a possible solution can only exist as a pair of seven and one of the remaining elements.
So again we are checking for minus five.
Now we look at the remaining parts and we see that in none of these places we have minus five right.
So again we move the pointer of I.
So it was over here and again we move it to the next one which is three.
Right.
So I at this point is three.
Now the needed value is target value minus three.
Right target value minus the ith value which is equal to minus one at this point.
So we are checking for minus one.
Again we only need to check the remaining parts.
We don't need to check what came before it.
Because again as we've already discussed, if what came before was part of the solution, it would already
have been caught in the previous iterations, right?
Because it was not caught.
So we don't need to care about these values.
We're only going to check only for the remaining parts.
Now the next value is minus one, right.
And when we see that three plus minus one that's two.
That's the needed value.
Right.
We were checking for minus one and we saw that minus one is there in the next value.
So we got our answer three plus minus one is equal to two.
And as the question asks us to return the indices don't return three and minus one rather than return
the indices two.
And three.
And that is our answer.
The answer is two comma three.
All right.
Now let's take a look at the complexity at the space and time complexity of this solution.
The brute force solution.
Now over here you can see that with I with the pointer I we are traversing the array once.
So if in the array there are n elements we would be doing n operations to traverse the array once with
the pointer I.
All right.
Now we can also see that at every iteration over here that is for every value of I we are again traversing
the array.
Right.
So again we have seen that I is traversing at this point I was I was pointing to the value two.
And at this point it was pointing to the value seven.
At this point it was pointing to the index with the value three.
Okay.
So it's pointing at the indices with the value two, seven, three, etc..
So we were traversing the array by changing this pointer.
Now at each I we are again traversing the array.
So that's what we did with the j pointer over here.
And so this is another n iteration.
So for every iteration over here and again we have n iterations over here.
For every n every one of these iterations we are doing n iterations again.
Right.
So that's why the time complexity of this solution is o of n into n, which is O of n square.
Now it's true that we are traversing only n minus one operations over here.
And when I was pointing to the value to the index one and it had the value seven, we were doing only
n minus two iterations over here.
But then we just need to know the trend right as the time for running the algorithm.
We are we are actually concerned with that, right?
We are concerned with the larger picture.
So that's why we are not exactly taking it as n minus one, n minus two, etc. in general, it's n iterations
for every iteration in the previous um traversing of the array.
So that's why the time complexity of this solution is O of n square.
Now what about the space complexity of the solution?
We can see that we are not storing anything extra, right?
We are not creating a new array or or using up space.
So the space complexity is O of one which is which is same as saying it runs in constant space.
So the time complexity is O of n square and the space is O of one.
Now O of n square is not a good time complexity right now.
Let's see in the next video whether we can do better than this.
Now a hint that we can take away from this is we can improve the time complexity by using more space.
And we will see how to do that with the hash table in the next video.