Welcome back.
Let's now think how we can solve this question in an efficient manner.
Let's say the matrix which is given to us is this one over here.
You can visualize it like this.
So you have four columns and you have three rows right.
So you can see you have three arrays over here inside the array.
So that's why you have three rows.
And then in each array you can see you have four elements.
So that's why you have four columns.
So the values are going to be 1234.
Then you have 5678 and nine 1011 and 12.
So this is the matrix which is given to us.
And let's say the target value is equal to five.
So what would be the brute force method of searching for the value target in the matrix which is given
to us.
So we could just go through each element right.
So we can go check.
Is this equal to five.
Is this equal to five etc..
Right.
So we could just go through each element.
Now if there are m rows and n columns then there are a total of m into n elements over here.
Right.
So you can see that in the worst case we would have to go through each of these elements.
So this method over here is not efficient.
All right.
So if there are m rows and n columns the time complexity of this approach would be o of m into n because
there would be m n elements over here.
Right.
So the time complexity of this would be o of m n.
Now this is not efficient.
Let's see how we can do better than this.
All right.
Now again this let's take another example.
Let's say this is the matrix which is given to us.
So you can see there are five rows and four columns.
And let's say the target is equal to 62.
Now over here the interesting thing is that every array over here is sorted.
And the last element in this array is going to be less than the first element in this array.
Right.
So we are going to make use of this to identify whether the given target is there in the matrix or not
in an efficient manner.
So let's try to think about the approach.
And again remember the clue over here is that we are going to use binary search.
And that's because the data over here is sorted.
Now first we are going to use binary search to find the relevant row in which the target value can be
there, if at all it is there.
All right.
So let's number the rows over here.
So we have 0123 and four.
So these are the indices for each of these five rows.
All right.
So we're going to do binary search to identify if at all which row can have the target value.
Now once we have identified the relevant row then we are going to do binary search on that row to check
if the target value is there in that row or not.
So this is the approach which we will follow to check for the target value in an efficient manner in
the matrix which is given to us.
So let's go ahead and try to walk through this.
So initially we have to identify the relevant row.
So we are going to say top is equal to zero.
And bottom is equal to four.
All right.
So top is equal to zero and bottom is equal to four.
So let's try to do binary search over here.
So we have to find middle.
Middle is going to be zero plus four divided by two.
And then we're going to floor it.
So that's equal to two right.
So middle is equal to two.
So that is this row over here.
All right.
So now we are going to check the least and the greatest value in the row which is the middle row.
All right.
So this row over here the least value is 25.
And the greatest value is 31.
Now if target is less than 25 which is the least value then we have to shift.
Then we have to shift bottom.
And if target is greater than the greatest value which is 31, then we have to shift the top.
So you can see we are doing nothing but binary search over here.
So if target is less than the least value, that means that we can just eliminate this half of the number
of rows.
Right.
And that means we can shift bottom to middle minus one which is this value over here.
Right.
So if target is less than 25 we can say bottom is equal to middle minus one which is eliminating this
half and shifting bottom to this row.
All right.
Now if this is not the case that is if target is greater than 31.
Right.
So that means we can eliminate this part and we can just shift top to this row over here.
That is we can say top is equal to middle plus one.
So you can see again this is nothing but binary search.
All right.
So let's go ahead with this example over here.
Now our target is 62.
And you can see that target is greater than 62.
Right.
Target is not less than 25.
So this is not true.
But target is greater than 31.
All right.
So we are going to set top is equal to middle plus one.
So top is going to be two plus one which is equal to three.
All right.
So we are getting top is equal to three and bottom is equal to four.
We again repeat.
So middle is going to be equal to top plus bottom by two.
And then we are flooring it.
So that's equal to three.
All right.
So that is this row over here.
Again we are going to check whether target is less than 32.
Is that true.
No target is 62 right.
That's not less than the lowest value.
So we don't need to go in this direction.
Now we are checking whether target is greater than 43.
Yes.
Target is greater than 43 right.
62 is greater than 43.
Right.
Therefore we will again shift top to middle plus one.
So top is going to be equal to middle which is three plus one which is four.
So we have eliminated this part.
All right.
So top is four and bottom is four.
So again we continue middle is going to be equal to top plus bottom by four.
And then we floor it.
So we get middle is four plus four by two which is equal to four.
All right.
Now in this row we have the lowest value which is 45.
And the largest value which is 65.
All right.
So again we proceed now is middle less than 45.
No.
Right.
So that's not true.
So middle the the target not the middle value.
The target is target less than 45.
No.
Is target greater than 65.
No.
Right.
So because target which is 62 is not less than the lowest value and not greater than the largest value,
we have found the row in which target can exist, if at all it exists.
Again, remember it's not necessary.
If target was 61, then you can see it's not over here.
But even in that case also we would have still identified the same row.
All right.
So we have identified the row in which the target value can be there, if at all.
It is there in the matrix which is given to us.
All right.
So let's proceed.
So, having identified that only this row is relevant, to check for the presence of the target value,
we are going to run binary search on this particular row over here, which is nothing but normal binary
search, which we have already previously discussed.
So let's go ahead and do that over here.
So the indices over here are 012 and three.
Now we are going to have a left pointer.
So left is going to be equal to zero.
And right is equal to three.
All right.
Now we are going to find the middle which is left plus right divided by two.
And then we are flooring it.
So zero plus three divided by two gives us 1.5.
And when we floor it we get middle is equal to one.
So that's pointing to this index over here.
All right.
So at index one the value is equal to 60.
Now 60 is not equal to the target value.
All right.
So we also see that 62 the target value is greater than the value at the index middle right which is
60.
So therefore we are going to shift left.
So we are going to shift left to middle plus one which is two.
So left is going to change from 0 to 2.
So left is two and right is at three.
Again we calculate the new middle which is two plus three divided by two.
And then we are flooring it.
So that's 2.5.
And then when we floor it we get two.
So middle is going to be equal to two which is this index over here.
And we can see that the target is equal to the value at the middle index.
And hence we have found the target.
And we can just return true.
So this is how we are going to solve this question in an efficient manner.
You can see that instead of doing m and m into n operations, which was the brute force approach over
here, we have to do only log m plus log N operations.
Right.
So that will be the time complexity of this solution.
Right.
So the time complexity, if there are m rows and n columns is equal to log m plus log n.
Now why log m.
That's to find the row right.
So to find the correct row we did a binary search with m elements which is the number of rows.
That's why we have log m over here.
And then we have log n over here which is done on that particular array.
Right.
Or the particular row.
So the array over here is having n elements which is the number of columns.
So that's why we have log n operations to do binary search on that particular row.
And log m plus log n is nothing but log m into n.
So the time complexity over here is o of log m n.
And what about the space complexity?
As we have implemented this iteratively, and as we are not using any auxiliary space, the space complexity
of this solution is O of one or constant space.