1
00:00:01,569 --> 00:00:02,630
Hello, everyone.

2
00:00:02,800 --> 00:00:08,290
So in this video, we are going to solve yet another question, and the name of the question is minimum

3
00:00:08,290 --> 00:00:10,320
steps and infinite grid.

4
00:00:10,870 --> 00:00:12,640
So we are given to the grid.

5
00:00:13,420 --> 00:00:15,450
So this is positive effects.

6
00:00:16,210 --> 00:00:22,130
This is positive of why this is negative X and this is negative.

7
00:00:22,130 --> 00:00:22,310
Right.

8
00:00:22,750 --> 00:00:26,190
So this is ah to the grid and this is basically a Infonet grid.

9
00:00:26,410 --> 00:00:28,720
So this is basically plus infinity.

10
00:00:29,110 --> 00:00:33,580
This is minus infinity plus infinity and this is minus infinity.

11
00:00:34,090 --> 00:00:37,990
Now the question is basically you are given order of points.

12
00:00:38,290 --> 00:00:39,990
For example, let me take one example.

13
00:00:40,000 --> 00:00:44,560
So you are given order in which you need to move.

14
00:00:47,030 --> 00:00:48,620
So let's say there are three points.

15
00:00:50,550 --> 00:00:57,330
This is your starting point, this is your end point you want to reach and point given the starting

16
00:00:57,330 --> 00:01:01,980
point and in this order, the order in which the points are given.

17
00:01:02,650 --> 00:01:07,320
So now there are eight directions in which I can move right.

18
00:01:07,560 --> 00:01:09,060
Matador's each direction.

19
00:01:09,390 --> 00:01:13,880
So from a point XCOM away, this is the first direction.

20
00:01:14,220 --> 00:01:15,450
This is the second direction.

21
00:01:15,630 --> 00:01:16,890
This is the third direction.

22
00:01:17,070 --> 00:01:19,380
This is the fourth and then fifth.

23
00:01:20,220 --> 00:01:22,840
Sixth, seventh and eighth.

24
00:01:23,250 --> 00:01:30,900
So in total, there are eight directions in which I can move from a given point, and now the question

25
00:01:30,900 --> 00:01:38,490
is basically given the end point, given the starting point and given all the points in-between, you

26
00:01:38,490 --> 00:01:43,800
need to move in this order and you need to tell me what are the minimum number of steps, which will

27
00:01:43,800 --> 00:01:48,870
be the minimum number of steps in which you will be able to reach the end point, given the starting

28
00:01:48,870 --> 00:01:49,240
point?

29
00:01:50,790 --> 00:01:52,410
Let me take this example only.

30
00:01:52,440 --> 00:01:54,980
So I am standing at point zero zero.

31
00:01:55,020 --> 00:01:56,250
This is the starting point.

32
00:01:57,180 --> 00:02:00,090
Let's say this is when this is to this three.

33
00:02:00,390 --> 00:02:01,620
Similarly, this is one.

34
00:02:01,830 --> 00:02:03,840
This is two and this is three.

35
00:02:04,230 --> 00:02:07,920
So this is one Komova at this point.

36
00:02:08,130 --> 00:02:11,190
And this is one, two, so one and two.

37
00:02:12,480 --> 00:02:15,230
So I want to reach at this point.

38
00:02:15,870 --> 00:02:16,410
Sorry.

39
00:02:18,110 --> 00:02:20,720
So I was saying, I want to reach this point.

40
00:02:22,110 --> 00:02:28,650
From this point, so first of all, I need to reach here so I can move diagonally and I will be able

41
00:02:28,650 --> 00:02:29,370
to reach here.

42
00:02:29,600 --> 00:02:31,340
So this is one step, right?

43
00:02:31,680 --> 00:02:32,920
This is one step.

44
00:02:34,350 --> 00:02:36,390
Now I want to reach one or two.

45
00:02:37,050 --> 00:02:38,280
I want to reach this point.

46
00:02:38,280 --> 00:02:40,230
From this point, I will take this step.

47
00:02:40,230 --> 00:02:42,730
I will move in this direction and I will take one step.

48
00:02:43,470 --> 00:02:45,010
So, again, one step.

49
00:02:45,420 --> 00:02:50,280
So my answer for this is basically total number of steps are basically two, right?

50
00:02:50,310 --> 00:02:51,440
One plus one.

51
00:02:51,810 --> 00:02:53,900
And these are the minimum number of steps.

52
00:02:54,810 --> 00:02:58,500
These are the minimum number of steps I will be able to reach at this point.

53
00:02:59,100 --> 00:03:04,650
The maximum number of steps can be you move in this direction, then you move in this direction, then

54
00:03:04,650 --> 00:03:06,690
you go here, then you go here.

55
00:03:06,990 --> 00:03:10,100
Then basically you reach here and then basically you reach here.

56
00:03:10,380 --> 00:03:13,320
So the maximum number of steps can be infinity eight.

57
00:03:13,650 --> 00:03:14,810
You will keep moving.

58
00:03:15,420 --> 00:03:17,700
So the maximum number of steps can be infinity.

59
00:03:17,730 --> 00:03:20,820
But we need to report our answer as the middle number of steps.

60
00:03:21,030 --> 00:03:25,160
So minimum number of steps for this given input is basically two.

61
00:03:25,820 --> 00:03:27,940
OK, so I hope you understood the question.

62
00:03:28,230 --> 00:03:31,530
So this will be the first step and this will be the second step.

63
00:03:32,580 --> 00:03:33,030
Right.

64
00:03:33,270 --> 00:03:35,800
Let me take one more example for better understanding.

65
00:03:36,420 --> 00:03:38,570
So let's take one more example.

66
00:03:41,720 --> 00:03:47,890
Now, in this case, let's take four to five points, so let me start with one comment.

67
00:03:48,260 --> 00:03:53,690
This is the starting point then I want to reach, let's say, three comadre, then let's say I want

68
00:03:53,690 --> 00:03:56,000
to reach Tecoma five.

69
00:03:56,570 --> 00:03:58,880
Then let's say I want to reach.

70
00:04:00,800 --> 00:04:02,010
Five camoflauge.

71
00:04:02,930 --> 00:04:09,840
OK, so this is our starting point and this is our end point and we need to move in this direction.

72
00:04:10,250 --> 00:04:15,680
So let me draw that to the grid here so that you will be able to understand better.

73
00:04:18,970 --> 00:04:21,220
So I have one to.

74
00:04:22,320 --> 00:04:34,290
Three and four and five, and similarly, here I have one, two, three and four, so when this is one

75
00:04:34,290 --> 00:04:38,220
and this is the next point is taken my three.

76
00:04:38,230 --> 00:04:40,170
So this is three and this is three.

77
00:04:41,880 --> 00:04:45,240
Next point is Tecoma five, so three and five.

78
00:04:45,270 --> 00:04:47,490
OK, let me extend this.

79
00:04:52,880 --> 00:04:57,140
So this is basically five next Monday's Tecoma five, three and five.

80
00:04:58,850 --> 00:05:02,660
And the next Monday's five or so, five and four.

81
00:05:04,190 --> 00:05:04,640
Right.

82
00:05:05,930 --> 00:05:10,790
So let's try to find out what will be the minimum number of points so from here.

83
00:05:11,000 --> 00:05:13,720
First of all, I need to reach here right in this way.

84
00:05:14,600 --> 00:05:17,540
So the number of steps forward mean a number of steps.

85
00:05:17,540 --> 00:05:19,910
But I will be doing I will try to move diagonally.

86
00:05:20,660 --> 00:05:21,010
Right.

87
00:05:21,100 --> 00:05:22,550
I will try to move diagonally.

88
00:05:22,940 --> 00:05:25,700
So if I will move diagonally, I will reach here.

89
00:05:27,900 --> 00:05:34,050
So this is one step, and then if I will move in this direction, then I will be able to reach at this

90
00:05:34,050 --> 00:05:34,440
point.

91
00:05:36,380 --> 00:05:37,730
These are two steps.

92
00:05:37,910 --> 00:05:44,200
OK, so this is the first step I will try to move diagonally forming a number of steps.

93
00:05:44,220 --> 00:05:44,880
What we will do.

94
00:05:44,900 --> 00:05:47,120
You will always try to move diagonally.

95
00:05:48,820 --> 00:05:55,420
Right, so I tried to move diagonally then after reaching this point, I cannot move diagonally, so

96
00:05:55,420 --> 00:05:56,890
I need to move in this direction.

97
00:05:56,900 --> 00:06:03,460
So two steps now from this point, I want to reach this point so I cannot move diagonally.

98
00:06:03,490 --> 00:06:03,860
Right.

99
00:06:04,320 --> 00:06:06,910
So what I will do, I will take one step in this direction.

100
00:06:08,490 --> 00:06:10,350
Then I will take one more step.

101
00:06:11,800 --> 00:06:13,210
So, again, two steps.

102
00:06:15,200 --> 00:06:15,620
Right.

103
00:06:17,340 --> 00:06:22,410
Now, at this point, I'm standing at this point and I want to reach this point, so let's see how many

104
00:06:22,410 --> 00:06:27,240
steps will be there again for me, the number of steps I will try to move diagonally.

105
00:06:27,780 --> 00:06:31,800
So if I will try to move diagonally, I will reach.

106
00:06:33,010 --> 00:06:34,480
I think at this point.

107
00:06:36,360 --> 00:06:36,790
Right.

108
00:06:37,560 --> 00:06:44,860
So this plane is basically your food coma for now after reaching this point.

109
00:06:45,780 --> 00:06:49,710
This is step one out, reaching this point where you will move in this direction.

110
00:06:51,480 --> 00:06:53,080
Because you cannot move diagonally here.

111
00:06:53,100 --> 00:06:54,130
So, again, two steps.

112
00:06:54,540 --> 00:06:57,040
So in total, two plus two plus two.

113
00:06:57,480 --> 00:06:59,680
So the answer for this question will be six.

114
00:07:00,240 --> 00:07:02,370
So our answer is going to be six.

115
00:07:04,800 --> 00:07:06,540
Now, how we can solve this question.

116
00:07:07,630 --> 00:07:11,200
So what you can do, you can post the video here and you can think of a solution.

117
00:07:13,110 --> 00:07:14,670
OK, so I hope.

118
00:07:16,620 --> 00:07:21,210
You have work up on this problem and you are able to find a solution if you are not able to find a solution.

119
00:07:21,240 --> 00:07:23,440
Now let's discuss what will be the solution.

120
00:07:23,820 --> 00:07:30,540
So given two points, let's say x1 vivan and x2 y2.

121
00:07:32,430 --> 00:07:38,160
What is the minimum number of steps in which I will be able to reach this point from this point?

122
00:07:39,570 --> 00:07:44,790
So for me, the number of steps, what we were doing, we will try to move diagonally.

123
00:07:46,500 --> 00:07:52,470
We will try to move diagonally, and if we are not able to move diagonally, then we will move in rest

124
00:07:52,470 --> 00:07:53,330
of the direction.

125
00:07:53,340 --> 00:07:56,140
This one, this one, this one or this one.

126
00:07:57,000 --> 00:07:58,110
So this is the approach.

127
00:07:58,320 --> 00:07:59,520
Let me take one example.

128
00:07:59,520 --> 00:08:02,970
Let's say from zero zero, you want to reach five cometary.

129
00:08:06,950 --> 00:08:14,600
From zero zero, this is one that says to this tree, this is one, this is two.

130
00:08:14,960 --> 00:08:15,790
This is three.

131
00:08:16,300 --> 00:08:17,420
This is four.

132
00:08:17,420 --> 00:08:18,770
And this is five.

133
00:08:20,360 --> 00:08:21,840
So five committees here.

134
00:08:22,670 --> 00:08:30,500
So our approach is first we will try to move diagonally, move diagonally, one step, move diagonally,

135
00:08:30,740 --> 00:08:33,860
one step, move diagonally, one step.

136
00:08:34,409 --> 00:08:39,169
OK, now from this point, I cannot move diagonally right now.

137
00:08:39,169 --> 00:08:40,450
I cannot move diagonally.

138
00:08:40,580 --> 00:08:43,100
So the only option is I will move in this direction.

139
00:08:43,190 --> 00:08:43,909
One step.

140
00:08:45,410 --> 00:08:49,550
And at this time, so in total, there will be five steps.

141
00:08:51,780 --> 00:08:52,200
Right.

142
00:08:52,620 --> 00:08:53,670
So what is the answer?

143
00:08:53,700 --> 00:08:59,400
The answer is basically first you will try to move diagonally and if you are not able to move diagonally,

144
00:08:59,400 --> 00:09:03,090
then you will move in this direction or this or this or this.

145
00:09:03,480 --> 00:09:06,960
So basically for this five minus zero.

146
00:09:09,110 --> 00:09:14,640
T minus zero five, minus zero three minus zero.

147
00:09:14,840 --> 00:09:18,560
OK, so what I'm doing x2 minus X1, right.

148
00:09:18,560 --> 00:09:23,030
This is what x2, this is your X1 and this is why do minus wavin.

149
00:09:23,990 --> 00:09:27,830
So this value is basically five and this value is basically three.

150
00:09:28,700 --> 00:09:31,880
So what we need to take we need to take the maximum of these two values.

151
00:09:32,180 --> 00:09:33,370
The maximum is five.

152
00:09:33,680 --> 00:09:35,570
So that's why you will take five steps.

153
00:09:36,830 --> 00:09:37,670
Simple, right?

154
00:09:37,850 --> 00:09:46,610
So the formula we have is basically from X and Y when I want to reach x2 y2, so the minimum number

155
00:09:46,610 --> 00:09:53,930
of steps will be you will subtract, you will take the difference and it will take the difference of

156
00:09:53,930 --> 00:09:55,070
vital minus wavin.

157
00:09:55,940 --> 00:09:58,210
And we need to take positive rate.

158
00:09:58,210 --> 00:09:58,220
Right.

159
00:09:58,820 --> 00:10:00,270
We will take positive value.

160
00:10:00,290 --> 00:10:03,700
So this will be absolute and this will be absolute.

161
00:10:04,040 --> 00:10:08,870
And what we need to do, we need to take the maximum of these to this value and this value.

162
00:10:08,870 --> 00:10:11,360
You can see we are taking the maximum of five entry.

163
00:10:11,990 --> 00:10:17,180
So our answer will be our answer will be take the maximum of this.

164
00:10:17,930 --> 00:10:20,930
So maximum of these two will be our answer.

165
00:10:22,190 --> 00:10:25,280
So let me use this formula and above quotients also.

166
00:10:27,690 --> 00:10:30,680
OK, so let's apply that formula.

167
00:10:32,180 --> 00:10:39,020
For discussion, so three minus one is two, three, minus two is one.

168
00:10:39,830 --> 00:10:42,740
So what is the maximum to do is maximum.

169
00:10:42,740 --> 00:10:43,830
So, too is our answer.

170
00:10:44,360 --> 00:10:47,540
Now for this three minus three zero.

171
00:10:48,900 --> 00:10:50,720
Five minus three is two.

172
00:10:51,660 --> 00:10:54,240
So what is the maximum value to use the maximum value?

173
00:10:54,240 --> 00:10:55,290
So I downsized to.

174
00:10:56,930 --> 00:11:02,070
Five entry differences to five and four differences one.

175
00:11:02,680 --> 00:11:04,640
Remember, we need to take positive value.

176
00:11:04,650 --> 00:11:06,040
We need to take absolute value.

177
00:11:06,050 --> 00:11:08,140
You will not do four minus five if you will not.

178
00:11:08,150 --> 00:11:08,380
Right.

179
00:11:08,390 --> 00:11:09,930
Minus one here, OK?

180
00:11:10,130 --> 00:11:12,010
We cannot move minus one step.

181
00:11:12,410 --> 00:11:14,390
We will move plus one step only.

182
00:11:15,080 --> 00:11:16,880
So differential five and four is one.

183
00:11:17,120 --> 00:11:19,640
Where is the maximum of two and one to a maximum.

184
00:11:19,800 --> 00:11:20,390
So two.

185
00:11:20,750 --> 00:11:24,410
And then we will basically add these values to plus two plus two.

186
00:11:24,740 --> 00:11:25,810
That will be your answer.

187
00:11:25,860 --> 00:11:26,340
Six.

188
00:11:26,540 --> 00:11:31,510
OK, so I hope you you got the solution.

189
00:11:31,820 --> 00:11:35,570
Now what to do next is you need to call the solution.

190
00:11:36,110 --> 00:11:42,860
So this question is basically present on interview a bit so you can go to the description of the question.

191
00:11:43,160 --> 00:11:49,190
And after going to the description of the question, you can write your solution here.

192
00:11:51,950 --> 00:11:58,160
So you can write your solution here, OK, after going through the description of the question, so

193
00:11:58,160 --> 00:12:03,560
in the next video we will be writing the code, but I highly recommend that you try calling this question

194
00:12:03,560 --> 00:12:04,080
yourself.

195
00:12:04,400 --> 00:12:06,670
OK, so this is it for this video.

196
00:12:06,710 --> 00:12:08,010
I will see you in the next one.

197
00:12:08,060 --> 00:12:08,600
Thank you.