Hello, everyone.
So in this video, we are going to solve yet another question, and the name of the question is minimum
steps and infinite grid.
So we are given to the grid.
So this is positive effects.
This is positive of why this is negative X and this is negative.
Right.
So this is ah to the grid and this is basically a Infonet grid.
So this is basically plus infinity.
This is minus infinity plus infinity and this is minus infinity.
Now the question is basically you are given order of points.
For example, let me take one example.
So you are given order in which you need to move.
So let's say there are three points.
This is your starting point, this is your end point you want to reach and point given the starting
point and in this order, the order in which the points are given.
So now there are eight directions in which I can move right.
Matador's each direction.
So from a point XCOM away, this is the first direction.
This is the second direction.
This is the third direction.
This is the fourth and then fifth.
Sixth, seventh and eighth.
So in total, there are eight directions in which I can move from a given point, and now the question
is basically given the end point, given the starting point and given all the points in-between, you
need to move in this order and you need to tell me what are the minimum number of steps, which will
be the minimum number of steps in which you will be able to reach the end point, given the starting
point?
Let me take this example only.
So I am standing at point zero zero.
This is the starting point.
Let's say this is when this is to this three.
Similarly, this is one.
This is two and this is three.
So this is one Komova at this point.
And this is one, two, so one and two.
So I want to reach at this point.
Sorry.
So I was saying, I want to reach this point.
From this point, so first of all, I need to reach here so I can move diagonally and I will be able
to reach here.
So this is one step, right?
This is one step.
Now I want to reach one or two.
I want to reach this point.
From this point, I will take this step.
I will move in this direction and I will take one step.
So, again, one step.
So my answer for this is basically total number of steps are basically two, right?
One plus one.
And these are the minimum number of steps.
These are the minimum number of steps I will be able to reach at this point.
The maximum number of steps can be you move in this direction, then you move in this direction, then
you go here, then you go here.
Then basically you reach here and then basically you reach here.
So the maximum number of steps can be infinity eight.
You will keep moving.
So the maximum number of steps can be infinity.
But we need to report our answer as the middle number of steps.
So minimum number of steps for this given input is basically two.
OK, so I hope you understood the question.
So this will be the first step and this will be the second step.
Right.
Let me take one more example for better understanding.
So let's take one more example.
Now, in this case, let's take four to five points, so let me start with one comment.
This is the starting point then I want to reach, let's say, three comadre, then let's say I want
to reach Tecoma five.
Then let's say I want to reach.
Five camoflauge.
OK, so this is our starting point and this is our end point and we need to move in this direction.
So let me draw that to the grid here so that you will be able to understand better.
So I have one to.
Three and four and five, and similarly, here I have one, two, three and four, so when this is one
and this is the next point is taken my three.
So this is three and this is three.
Next point is Tecoma five, so three and five.
OK, let me extend this.
So this is basically five next Monday's Tecoma five, three and five.
And the next Monday's five or so, five and four.
Right.
So let's try to find out what will be the minimum number of points so from here.
First of all, I need to reach here right in this way.
So the number of steps forward mean a number of steps.
But I will be doing I will try to move diagonally.
Right.
I will try to move diagonally.
So if I will move diagonally, I will reach here.
So this is one step, and then if I will move in this direction, then I will be able to reach at this
point.
These are two steps.
OK, so this is the first step I will try to move diagonally forming a number of steps.
What we will do.
You will always try to move diagonally.
Right, so I tried to move diagonally then after reaching this point, I cannot move diagonally, so
I need to move in this direction.
So two steps now from this point, I want to reach this point so I cannot move diagonally.
Right.
So what I will do, I will take one step in this direction.
Then I will take one more step.
So, again, two steps.
Right.
Now, at this point, I'm standing at this point and I want to reach this point, so let's see how many
steps will be there again for me, the number of steps I will try to move diagonally.
So if I will try to move diagonally, I will reach.
I think at this point.
Right.
So this plane is basically your food coma for now after reaching this point.
This is step one out, reaching this point where you will move in this direction.
Because you cannot move diagonally here.
So, again, two steps.
So in total, two plus two plus two.
So the answer for this question will be six.
So our answer is going to be six.
Now, how we can solve this question.
So what you can do, you can post the video here and you can think of a solution.
OK, so I hope.
You have work up on this problem and you are able to find a solution if you are not able to find a solution.
Now let's discuss what will be the solution.
So given two points, let's say x1 vivan and x2 y2.
What is the minimum number of steps in which I will be able to reach this point from this point?
So for me, the number of steps, what we were doing, we will try to move diagonally.
We will try to move diagonally, and if we are not able to move diagonally, then we will move in rest
of the direction.
This one, this one, this one or this one.
So this is the approach.
Let me take one example.
Let's say from zero zero, you want to reach five cometary.
From zero zero, this is one that says to this tree, this is one, this is two.
This is three.
This is four.
And this is five.
So five committees here.
So our approach is first we will try to move diagonally, move diagonally, one step, move diagonally,
one step, move diagonally, one step.
OK, now from this point, I cannot move diagonally right now.
I cannot move diagonally.
So the only option is I will move in this direction.
One step.
And at this time, so in total, there will be five steps.
Right.
So what is the answer?
The answer is basically first you will try to move diagonally and if you are not able to move diagonally,
then you will move in this direction or this or this or this.
So basically for this five minus zero.
T minus zero five, minus zero three minus zero.
OK, so what I'm doing x2 minus X1, right.
This is what x2, this is your X1 and this is why do minus wavin.
So this value is basically five and this value is basically three.
So what we need to take we need to take the maximum of these two values.
The maximum is five.
So that's why you will take five steps.
Simple, right?
So the formula we have is basically from X and Y when I want to reach x2 y2, so the minimum number
of steps will be you will subtract, you will take the difference and it will take the difference of
vital minus wavin.
And we need to take positive rate.
Right.
We will take positive value.
So this will be absolute and this will be absolute.
And what we need to do, we need to take the maximum of these to this value and this value.
You can see we are taking the maximum of five entry.
So our answer will be our answer will be take the maximum of this.
So maximum of these two will be our answer.
So let me use this formula and above quotients also.
OK, so let's apply that formula.
For discussion, so three minus one is two, three, minus two is one.
So what is the maximum to do is maximum.
So, too is our answer.
Now for this three minus three zero.
Five minus three is two.
So what is the maximum value to use the maximum value?
So I downsized to.
Five entry differences to five and four differences one.
Remember, we need to take positive value.
We need to take absolute value.
You will not do four minus five if you will not.
Right.
Minus one here, OK?
We cannot move minus one step.
We will move plus one step only.
So differential five and four is one.
Where is the maximum of two and one to a maximum.
So two.
And then we will basically add these values to plus two plus two.
That will be your answer.
Six.
OK, so I hope you you got the solution.
Now what to do next is you need to call the solution.
So this question is basically present on interview a bit so you can go to the description of the question.
And after going to the description of the question, you can write your solution here.
So you can write your solution here, OK, after going through the description of the question, so
in the next video we will be writing the code, but I highly recommend that you try calling this question
yourself.
OK, so this is it for this video.
I will see you in the next one.
Thank you.