Hi, everyone.
So today we are going to discuss this question so rich in Matrix.
OK, so input will basically be a matrix and our target value that we have to search inside the Matrix.
OK, but this matrix is not a normal matrix.
OK, so this is not a normal matrix.
The Matrix has a property which is the property.
So this matrix, each rule is sorted.
And each column is sorted.
OK, so you can see so this is sorted two, six, seven, 11.
This is a sorted row, three, eight, 10, 12.
This is a sorted row for nine, 11, 13.
This is a sorted five, 15, 16 and 18.
OK, so in this matrix, each are always sorted in descending order.
And similarly, each column is a sorted.
OK, so this is two, then three, then four and then five.
Similarly, six, eight, nine, 15, seven, 10, 11 and 16.
Sorted 11, 12, 13 and 18.
OK, so each row and column in the government is basically sorted and the question is basically given
our target value.
So in this case, the target values nine.
So given a target value, we have to return, true or false.
So we will we have to return double in value.
So this value will be true if the given target is present inside the Matrix, and this will default
if the given target value is not present inside The Matrix.
OK, so this question is basically present on later.
OK, so you can see here.
OK, so each rule is sorted and each column is sorted.
OK, so how we can solve this question.
So the first one ways to solve this question, let us discuss the approaches.
So the first approach is the brute force approach.
OK, so what this approach will say is just iterate over all the metrics, just outraged over the Matrix,
basically go through all the elements, if you will, find the target value, don't draw.
Otherwise it involves.
OK, so we will go through each and every element.
So what will be the time complexity.
So let's say the dimensions of the Matrix are I'm in Darwin, so the time complexity will be Emman and
the space complexity will be alderwoman.
OK, so this brute forces go through each and every element in the matrix and compared that element
with the target value.
OK, if you found a target value redrado as it unfolds.
So this is the time when this space complexity, the second approach is basically binary search, binary
search each arrow.
OK, so we can see each arrow is a sorted row.
So we will go through the first rule, we will apply the binary search, come to the second rule, apply
the binary search, come to the third row applied by the result, come today for true applied binary
search.
So we are iterating over the rules so that time complexity will be so since we are dating over the rules.
So we have Amaru's and for searching what we are doing.
So this is basically in columns, therefore searching.
We are using binary search.
So it will be emond to login and to login because we are using binary search.
OK, so we are optimizing our time, complexity and virtual space complexity.
So still, this is our Ardavan.
OK, now let's discuss the best approach.
So this is this method is called staircase search.
OK, this is called staircase search.
Now, what this method says is basically you move at the move, at this element, basically the opposite
element.
OK, so move to the top right element.
Move to the top, right?
So this is 11 now, compared 11 with nine, so 11 is bigger than move left.
OK, compare seven with nine, so this is a smaller move down.
Now, compare ten with nine, so ten is bigger than move left.
Now, compare it with nine so it is smaller, move down now, compare nine with nine to return.
True.
OK, so it says move their top rate element now compared the element.
With the target value, so if that element is greater than the target value, what we will do.
So basically you will move left.
So for moving left, we will do column minus minus.
OK.
And if the element is smaller, then the target value we have to move down.
OK, so for moving down, I will do rule plus plus.
OK, so this is 11 11 element.
So the element is greater than the target value then where the nine will obviously nine will lie in
the left hand side because the left hand side of the 11, the elements are smaller.
We cannot move down because if we will move down then all the elements will be greater than 11 and we
have to find nine.
OK, so nine element can only be present in the left hand side of the 11.
Now, compare seven with the nine, so seven element is smaller than nine, if you will move left,
then you will get smaller element, then seven, OK, because that rule is sorted.
So we cannot move left.
We can only move down now, compared then with the nine.
So 10 is bigger.
If you will move down, you will get bigger element then.
Then but we have to find nine.
So the only option is to move left and it is smaller than nine.
So obviously you cannot move left.
If you will move left, you cannot you can never find nine.
So the only option is to move down.
OK, so this staircase approach, this staircase approach is basically making the use of the property
of the Matrix Room and Colombo times.
OK, and now why it is called staircase approach because you can see.
So this resembles the staircase.
OK, so this shape, the way in we are searching.
This is nothing.
This is just a staircase.
So that's why it is called a staircase approach.
OK, and the logic is very simple.
If the current element is greater than the target value, then obviously you have to move left.
If you want to find out the target, well, you cannot move down.
So moving left, I am doing minus minus.
And this is the case.
Obviously, the only thing, the only way to find out the target value if we will move down so far moving
down I'm being replaced is very simple now over the time and the space complexity for using this approach.
So space complexity is nothing.
This will be a drama and complex complexity is basically in the worst case, what will happen.
So I will go through this and then I will go through this.
So in the worst case, complexity will be emplacing when the element is not present.
OK, so you can see.
First, our time complexity was immense.
Now it is linear emplacing.
OK, so this is also an example.
Let us use this approach in this example so we have to find the target value five.
OK, so let me draw here.
So I have one for seven, 11, 15, then to three, then 18, five, six, 13 and 21, eight, nine,
14, 23, well, 16, 17, 26, 19, 22, 24 and 30.
OK, so the target value is basically five.
So according to staircase approach, come here at the top right now, compare 15 with three.
So obviously 15 is bigger.
So the only way to find five is to move left.
Again, 11 is bigger than five.
So only way is to find five is basically move left again.
Seven is greater than five.
So five can lie on the left hand side.
So move to the left.
Now compare four with five.
Obviously, the fifth element can represent downside only.
So move down.
And now we will get our element five.
So we will return to.
OK, now let's find out the settlement, which is 20, OK, so I am standing here 15.
So if you want to find 20, you will move down because if you will move down, you will get all the
elements which are good than 15.
So move down.
So 19, obviously, if you want to find out, 20, move down.
So I will move down now.
22 is bigger.
So move left.
16 is smaller.
So move down.
17 is smaller.
Move down.
This bigger move left 23 is a bigger move left.
21 is bigger than 20 moved left.
18 is smaller than 20 moved down.
OK, so if you will move down, I want my tax will finish and we will stop.
And what we will do, we will return.
False.
OK, so you can see this is a staircase approach.
This resembles the shape of a staircase.
OK, so that's where this method of searching is called staircase.
OK, so now, since you have understood the logic, I think chording will not be a problem.
OK, so now let us write the code.
OK, so the court will be very, very simple, so now let us find out the rules and the columns.
OK.
So it is basically how many rules are there?
So this is matrix size.
And now let's find out the columns.
So this is nothing but mattocks of zero dollars.
OK, so let us handle first case, so if the target value is basically smaller than.
The smallest value in the Matrix.
OK, so you can see.
This is basically the smallest element in the Matrix.
OK, this will be the smallest element of the Murdochs because it will move right or you will move down,
the elements will increase.
And similarly, this is the largest element.
So this is the largest element of this matrix and this is the smallest element.
OK.
So basically, if the target value is smaller, then the smallest element of the matrix or the target
value is basically bigger than the biggest, the largest element in the matrix.
So this is basically euros minus one.
And Collins, minus one.
So if the target value is greater than the largest value, then obviously you can directly return false
because the element will not be present.
OK, OK, so now let us trade over the metrics.
OK, so.
Let us take two variables, so.
I the satellite letter, Tawadros and I have a very bulgy, so this will add it over the columns, so
this is nothing but so I have to move to the last column.
So this is columns minus one.
OK, so what the condition?
So while Daryl Savelli is less than construes minus one.
And.
While is basically greater than or equal to zero.
OK, so what I have to do compared the current element.
So this is basically I am moving to the top right corner.
OK, so move to the top.
Right.
And since I have to do so, I will do plus plus I, I will look on a minus minus.
So that's why this condition, because I will luchador plus plus.
And that's why this condition because I would look whams minus minus.
OK, so if the current element.
Which is.
Networks of AIG.
So there are three cases, first cases very simple, we found out the target element, so in this case,
I can return.
True.
OK, you can see the return type Izabel.
So I have to return either true or false.
So if you have found the element, the target element we can return to.
Now, there are two more cases.
The second case can be.
If the current element is smaller than the target value.
Then would I have to do I have to move down so far, moving down, I have to rob placeless.
OK, so the name of the variable is basically I so I will do a placeless.
And in the terrorist case.
So if the current element is getting their target value, then we'd have to do so, I have to move left.
So for moving left, I have to do a column minus minus.
So here the variable column is basically variable G, OK, and if I reach the end of the loop, I can
return false.
Basically the target value is not present.
OK.
OK, so now let us submit our good.
OK, so if our taxes and we are getting a random error.
OK, so what I have to do, I have to handle the situation here.
So if basically Rose is zero, if there are not any rules, what can I do?
I can return false.
So, again, if the columns are zero, then I can also read Danville's.
OK, so our goal is working, so as we discussed the time and the space complexity for using this takes,
approaches, spaces or driven and time is Ampligen.
OK.
So if you're an out, you can ask me, OK, thank you.