1
00:00:01,940 --> 00:00:02,640
Hi, everyone.

2
00:00:02,660 --> 00:00:08,360
So in this video, we are going to solve this question jump game, so what is the question?

3
00:00:08,630 --> 00:00:09,730
So what is the question?

4
00:00:09,790 --> 00:00:11,000
The question is very simple.

5
00:00:11,010 --> 00:00:13,130
You will be provided with a non-negative integers.

6
00:00:13,130 --> 00:00:15,400
That means positive integers, including zero.

7
00:00:15,770 --> 00:00:22,170
So you have an array at different ages and you are initially at the first index.

8
00:00:22,190 --> 00:00:22,550
OK.

9
00:00:23,710 --> 00:00:30,250
So this is the first index and this is the last index, initially, you are first index initial evaluation

10
00:00:30,250 --> 00:00:31,660
that the first index of the area.

11
00:00:32,110 --> 00:00:36,130
Now each element in the area represent the maximum jump that I can take.

12
00:00:36,730 --> 00:00:39,270
For example, if let's say this is two.

13
00:00:39,510 --> 00:00:46,060
OK, so this to me is I can take a jump of one or I can take a jump of the maximum.

14
00:00:46,060 --> 00:00:47,440
I can take a jump of two.

15
00:00:47,800 --> 00:00:48,610
So basically.

16
00:00:50,160 --> 00:00:56,340
Let's say the name of this ad is basically name, so number five means the maximum jump I can take is

17
00:00:56,340 --> 00:00:57,780
basically name of a.

18
00:00:59,860 --> 00:01:03,550
So and these jumps are also possible less than a Muffie.

19
00:01:03,770 --> 00:01:08,710
OK, and we have to remain whether we can reach the last position or not.

20
00:01:09,220 --> 00:01:10,750
Let us consider this example.

21
00:01:12,190 --> 00:01:15,640
So I have two, three, then one went in for.

22
00:01:17,790 --> 00:01:19,010
I have to reach the last.

23
00:01:19,470 --> 00:01:21,760
Currently, I am present at the first index.

24
00:01:21,810 --> 00:01:22,890
Now this is Valetta.

25
00:01:23,490 --> 00:01:24,890
So there are two possibilities.

26
00:01:24,900 --> 00:01:31,440
I can take a jump of one and I can reach three, or I can take a jump off two and I can reach one.

27
00:01:31,810 --> 00:01:34,360
OK, let us consider both the options.

28
00:01:34,380 --> 00:01:39,970
OK, so if this is the first option, let's say I am taking a jump of one so I will reach three.

29
00:01:40,560 --> 00:01:46,830
So from three what I can do, I can take a jump of three and I can reach for ok, I can take a jump

30
00:01:46,830 --> 00:01:48,100
of three and I can reach for.

31
00:01:48,270 --> 00:01:50,630
So in this case my output will be true.

32
00:01:50,980 --> 00:01:55,150
OK, I have to return a boolean value you can see after the double in value.

33
00:01:55,170 --> 00:02:00,090
So since I am able to reach the last index, I will return to simple.

34
00:02:00,330 --> 00:02:02,130
Now if it will take a jump of two.

35
00:02:03,430 --> 00:02:08,509
This is the second option if you take a bottle now from one that makes them jump, you can take is one.

36
00:02:09,070 --> 00:02:12,630
Now, again, from when the maximum you can take is also one.

37
00:02:12,860 --> 00:02:18,410
OK, so if you will follow the second option also, then also you are able to reach the last Hynix,

38
00:02:18,490 --> 00:02:23,200
OK, so you can either take a jump of one or you can either take a jump of two.

39
00:02:23,200 --> 00:02:26,960
You are able to reach the last or next since you are able to reach the next year.

40
00:02:26,980 --> 00:02:28,480
Also in this case will be through.

41
00:02:29,900 --> 00:02:30,440
Simple.

42
00:02:31,860 --> 00:02:39,720
Now, let us consider this example, I have three, two, one, zero and four, I am standing here at

43
00:02:39,720 --> 00:02:42,450
the first position and I want to reach the last index.

44
00:02:42,780 --> 00:02:45,540
So let's say I'm digging a jump of index three.

45
00:02:46,050 --> 00:02:48,290
Sorry, I'm taking a jump of three.

46
00:02:48,720 --> 00:02:50,870
So if I'm taking a jump of three, I will reach a zero.

47
00:02:51,120 --> 00:02:53,090
So from zero, I cannot take any jump.

48
00:02:53,340 --> 00:02:55,140
So this method is wrong.

49
00:02:55,150 --> 00:02:56,940
I'm not able to reach the last index.

50
00:02:58,010 --> 00:03:04,610
Now, if I take a jump off two, I will reach one, so from one, I can only take a jump of one, so

51
00:03:04,610 --> 00:03:05,520
I will reach a zero.

52
00:03:05,720 --> 00:03:08,670
So again, from zero, we cannot reach the last index.

53
00:03:08,690 --> 00:03:10,160
So this option is also wrong.

54
00:03:10,820 --> 00:03:19,550
Now, if I take a jump of one now from two, I can take a jump of one or I can jump off to if I will

55
00:03:19,550 --> 00:03:21,830
take a jump of two, I will reach zero.

56
00:03:22,130 --> 00:03:24,190
And from zero I cannot go anywhere else.

57
00:03:24,230 --> 00:03:25,070
So this is wrong.

58
00:03:25,280 --> 00:03:29,880
If I take a jump of one, I will reach one and from when I can only take a jump of one.

59
00:03:29,900 --> 00:03:33,180
So this is also wrong because we will reach a zero again.

60
00:03:33,500 --> 00:03:36,860
So in this case, there is no way I can reach the last index.

61
00:03:37,870 --> 00:03:42,190
There's no way to reach the last index, so in this case, my output will be false.

62
00:03:42,240 --> 00:03:44,180
OK, my output will be false.

63
00:03:44,200 --> 00:03:45,880
I have to return a boolean value.

64
00:03:46,420 --> 00:03:51,790
And in this case, I will return false because there is no way for us to reach the last index starting

65
00:03:51,790 --> 00:03:52,820
from the first index.

66
00:03:53,560 --> 00:03:55,200
So how we can solve this question.

67
00:03:56,200 --> 00:04:02,290
So basically the main idea behind solving this question, the main idea behind this question is basically

68
00:04:02,290 --> 00:04:06,640
let us define two indexes, so let us take two times good index.

69
00:04:07,270 --> 00:04:10,530
And the second term is basically bad index.

70
00:04:10,780 --> 00:04:16,890
So what does the meaning of good index so good index means that index from which we can reach the Lastra

71
00:04:16,899 --> 00:04:20,110
index from which we can reach last index.

72
00:04:20,440 --> 00:04:22,720
OK, and what is a bad index.

73
00:04:23,020 --> 00:04:25,540
So bad index is just the opposite of good index.

74
00:04:25,900 --> 00:04:34,900
OK, so this is the index from which we cannot reach Lastra index, so we are defining to dumps good

75
00:04:34,900 --> 00:04:36,010
index and index.

76
00:04:36,850 --> 00:04:39,950
Now let's discuss the main idea behind solving this question.

77
00:04:40,480 --> 00:04:41,320
So if.

78
00:04:42,130 --> 00:04:45,380
You are standing so there is current position.

79
00:04:45,470 --> 00:04:49,260
OK, you are standing at this position, so let's name it current position.

80
00:04:50,020 --> 00:04:52,090
So if current position plus.

81
00:04:53,320 --> 00:04:57,540
NAMS is the name of the ad, OK, so you can see them, says the name of the ad.

82
00:04:58,630 --> 00:05:05,430
So if no, if current operation listen so far, so far is basically the maximum that I can pick.

83
00:05:05,530 --> 00:05:14,500
So if current position bless them, Sophi is greater than or equal to last most good index, then what

84
00:05:14,500 --> 00:05:15,130
is the meaning?

85
00:05:15,160 --> 00:05:18,590
OK, so what we can draw from here, what will be the result.

86
00:05:18,880 --> 00:05:23,920
So the result will be basically the current position is also a good index.

87
00:05:24,070 --> 00:05:26,380
Current position is also a good index.

88
00:05:26,890 --> 00:05:29,780
OK, if you will understand this thing, then the question is solid.

89
00:05:29,920 --> 00:05:31,480
So I'm repeating myself.

90
00:05:31,510 --> 00:05:36,400
You are standing at the current position and if you need the current position, so if current position

91
00:05:36,400 --> 00:05:40,210
plus Nimsoft, OK, current position plus.

92
00:05:40,220 --> 00:05:44,680
So this would be basically this is not a this is basically current position only.

93
00:05:44,750 --> 00:05:45,130
OK.

94
00:05:47,630 --> 00:05:53,780
So you are standing at the current position, if the maximum jump you can take is basically Nimsoft

95
00:05:53,780 --> 00:06:00,080
current position, so if current position plus Nimsoft current position is greater than or close to

96
00:06:00,410 --> 00:06:03,100
the last most or you can say the rightmost.

97
00:06:03,590 --> 00:06:07,100
So if this is good, then close to rightmost the good next.

98
00:06:08,420 --> 00:06:12,040
Then the current position is also a good index, obviously.

99
00:06:12,310 --> 00:06:14,060
OK, just try to think carefully.

100
00:06:14,060 --> 00:06:15,000
I'm repeating myself.

101
00:06:15,020 --> 00:06:16,700
You're standing at the current position.

102
00:06:17,450 --> 00:06:21,910
The maximum jump you can take is basically Nemstov current position, OK?

103
00:06:21,920 --> 00:06:24,700
The maximum you can take is basically Nimsoft current position.

104
00:06:25,130 --> 00:06:32,870
So if this thing if this thing is basically graded then or goes to the rightmost good index.

105
00:06:33,960 --> 00:06:40,920
That means the current position is also good and it's very, very simple now we will use this approach

106
00:06:40,920 --> 00:06:42,000
to solve the question.

107
00:06:43,130 --> 00:06:46,610
OK, we will use this approach to solve this question, let us take an example.

108
00:06:47,490 --> 00:06:49,630
Let's take this example two three one one four.

109
00:06:50,120 --> 00:06:52,390
OK, let us take this example.

110
00:06:52,850 --> 00:06:56,730
So two, then three, then one, then one, then four.

111
00:06:56,990 --> 00:06:58,460
So what is my rightmost?

112
00:06:58,460 --> 00:06:59,040
Good index.

113
00:06:59,240 --> 00:07:00,770
So this is the rightmost.

114
00:07:00,780 --> 00:07:01,430
Good index.

115
00:07:01,790 --> 00:07:04,790
OK, so this is the rightmost good index.

116
00:07:05,510 --> 00:07:06,470
Now start from here.

117
00:07:06,470 --> 00:07:08,510
We will traverse the error in the backward direction.

118
00:07:09,320 --> 00:07:12,410
So you are standing at one, you are standing at this index.

119
00:07:12,420 --> 00:07:15,750
So this is zero one, two, three and four.

120
00:07:16,370 --> 00:07:19,520
So currently the eight most good index is basically four.

121
00:07:20,300 --> 00:07:25,920
You are standing at index three, OK, you're standing at index three, the maximum number you can take.

122
00:07:25,940 --> 00:07:31,610
OK, so current position plus Nimsoft, I saw three is the current position plus nothing so far is basically

123
00:07:31,610 --> 00:07:31,830
one.

124
00:07:32,150 --> 00:07:35,620
So three plus one is basically greater than or equal to four.

125
00:07:35,930 --> 00:07:38,600
That means this is also a good index.

126
00:07:38,600 --> 00:07:41,020
So I will update my last most good index.

127
00:07:41,030 --> 00:07:43,310
So what I will do, I will argue will come here.

128
00:07:44,340 --> 00:07:45,520
Right, good index.

129
00:07:45,730 --> 00:07:51,310
OK, so my ablated are just basically three since we are trading over the area, I will reach here.

130
00:07:51,340 --> 00:07:52,850
So this index is basically two.

131
00:07:53,230 --> 00:07:55,000
So two plus one.

132
00:07:55,570 --> 00:07:57,940
So again, this is basically Gardino close to three.

133
00:07:57,940 --> 00:07:59,610
That means this is also a good index.

134
00:07:59,620 --> 00:08:01,030
So I will update Miyaji.

135
00:08:02,010 --> 00:08:09,330
OK, so now the charges basically do now come here, so the index is basically one and the value is

136
00:08:09,330 --> 00:08:10,040
basically three.

137
00:08:10,050 --> 00:08:12,720
So when close to identical to do.

138
00:08:12,960 --> 00:08:14,330
OK, so this is also true.

139
00:08:14,340 --> 00:08:15,870
So R.G. will come here.

140
00:08:15,870 --> 00:08:16,560
Right here and.

141
00:08:16,660 --> 00:08:16,990
Right.

142
00:08:17,010 --> 00:08:18,120
Good index will come here.

143
00:08:19,290 --> 00:08:26,460
Now I'm standing here, so this is zero zero close to what is our DUI charges, basically one so zero

144
00:08:26,460 --> 00:08:27,930
plus two is getting close to one.

145
00:08:27,930 --> 00:08:30,470
That means this is the r.g OK.

146
00:08:30,630 --> 00:08:33,000
And finally my arrival and OK.

147
00:08:33,270 --> 00:08:34,650
And where is R.G.?

148
00:08:34,650 --> 00:08:36,870
So R.G. is basically at the next to zero.

149
00:08:37,169 --> 00:08:39,960
OK, so basically index zero.

150
00:08:40,020 --> 00:08:41,159
What is an index zero?

151
00:08:41,490 --> 00:08:43,220
Zero is basically a good index.

152
00:08:43,230 --> 00:08:45,840
OK, and Texada is basically a good index.

153
00:08:46,050 --> 00:08:47,880
And what is the meaning of good index.

154
00:08:48,980 --> 00:08:56,360
So good index is that index from where I can reach the last index, since zero is a good index, that

155
00:08:56,360 --> 00:08:58,970
means I will be able to reach the last position.

156
00:08:58,970 --> 00:09:00,230
So I will return to.

157
00:09:01,170 --> 00:09:05,800
So I will return through simple let's take one more example in that case.

158
00:09:05,820 --> 00:09:07,680
So let's take this example.

159
00:09:07,770 --> 00:09:10,410
In this case, I will not be able to reach the last minute.

160
00:09:10,640 --> 00:09:12,000
So three two one zero four.

161
00:09:13,270 --> 00:09:14,350
Three two one zero four.

162
00:09:14,500 --> 00:09:18,200
So in this example, basically, every index is basically good index.

163
00:09:18,320 --> 00:09:20,080
OK, every index is good index.

164
00:09:21,040 --> 00:09:26,350
Now, I am taking this example, three two one zero four three two, one, zero and four.

165
00:09:26,480 --> 00:09:29,580
OK, so this is my good index initially.

166
00:09:30,010 --> 00:09:32,000
So this is basically index.

167
00:09:32,000 --> 00:09:34,210
So zero one, two, three and four.

168
00:09:34,690 --> 00:09:35,680
So this is good.

169
00:09:35,680 --> 00:09:36,880
Index is basically four.

170
00:09:37,140 --> 00:09:38,380
OK, now come here.

171
00:09:38,680 --> 00:09:41,950
So this is an index T, so index three plus zero.

172
00:09:42,100 --> 00:09:46,930
What I'm doing current position plus number of current position.

173
00:09:46,960 --> 00:09:50,400
OK, so triple zero, is it good then or close to four.

174
00:09:50,450 --> 00:09:51,990
No this is not true.

175
00:09:52,540 --> 00:09:54,520
So that means this is a bad index.

176
00:09:55,330 --> 00:09:56,710
OK, now come here.

177
00:09:57,190 --> 00:10:02,600
So this is an index to show two plus one is guerdon or equal to four.

178
00:10:02,990 --> 00:10:04,160
No, this is not true.

179
00:10:04,180 --> 00:10:06,160
So that means this is also about index.

180
00:10:07,510 --> 00:10:08,350
Malcolm here.

181
00:10:09,810 --> 00:10:18,420
So this is basically two sorry, next one, so superannuation is one plus maximum I can take is basically

182
00:10:18,420 --> 00:10:18,660
two.

183
00:10:19,320 --> 00:10:23,190
So one plus two is Tehsil is triggered, then Noriko's to vote no.

184
00:10:24,000 --> 00:10:27,220
So this is also about bad index now comes here.

185
00:10:27,540 --> 00:10:30,260
So this is like zero zero zero plasty.

186
00:10:31,110 --> 00:10:32,150
So is it good then.

187
00:10:32,160 --> 00:10:33,060
Articles to for.

188
00:10:33,060 --> 00:10:33,480
No.

189
00:10:34,610 --> 00:10:36,830
So that means this is also about index.

190
00:10:37,100 --> 00:10:39,980
And finally, finally, I will reach the minus one index.

191
00:10:40,010 --> 00:10:41,390
OK, so then I will stop.

192
00:10:42,050 --> 00:10:44,190
So what is the gold index?

193
00:10:44,390 --> 00:10:46,870
So basically, I have to check for the first index only.

194
00:10:46,880 --> 00:10:48,800
So is the first index a good index?

195
00:10:48,830 --> 00:10:49,660
What about index?

196
00:10:49,760 --> 00:10:50,950
It is a bad index.

197
00:10:51,260 --> 00:10:55,850
So basically the first operation, the point at which I am standing index zero.

198
00:10:56,090 --> 00:10:58,310
So this is basically a bad index.

199
00:10:58,580 --> 00:10:59,960
And what is the meaning of bad?

200
00:10:59,960 --> 00:11:00,620
Bad means?

201
00:11:00,620 --> 00:11:03,210
I will not be able to reach the last index.

202
00:11:03,650 --> 00:11:08,420
OK, I will not be able to reach the last index, so I will return for in this case.

203
00:11:08,570 --> 00:11:10,790
So this is the only good index here.

204
00:11:11,660 --> 00:11:13,370
This is the only good index here.

205
00:11:13,490 --> 00:11:19,610
The index for is the only good index from basically from index four you can reach index for OK, from

206
00:11:19,610 --> 00:11:21,290
index four you can reach index four.

207
00:11:21,560 --> 00:11:24,230
But from index zero you cannot reach index four.

208
00:11:25,190 --> 00:11:31,130
From index one you cannot reach index four from index to you cannot reach index four from index three,

209
00:11:31,130 --> 00:11:32,480
you cannot reach index four.

210
00:11:32,520 --> 00:11:35,930
OK, so all these are bad indexes.

211
00:11:36,320 --> 00:11:38,120
All these are bad indexes.

212
00:11:39,420 --> 00:11:40,890
So I hope you understood the logic.

213
00:11:41,100 --> 00:11:46,620
So basically, they mean the idea behind this caution is basically to understand this thing, OK, if

214
00:11:46,620 --> 00:11:51,210
you're standing at the current position, if you will, and I'm writing again, OK?

215
00:11:53,120 --> 00:11:58,730
I am writing again, so I hope you understood the meaning of the last, the good and the bad index.

216
00:11:58,760 --> 00:12:04,070
OK, so if the current position, if you're standing at the current position, what is the maximum jump

217
00:12:04,070 --> 00:12:04,700
you can take?

218
00:12:04,700 --> 00:12:07,760
The maximum you can take is basically Nemstov current position.

219
00:12:07,770 --> 00:12:14,270
So if this thing is basically greater than or equal to the rightmost, good index, the rightmost,

220
00:12:14,270 --> 00:12:15,050
good index.

221
00:12:15,290 --> 00:12:17,770
Good index is the index from where you can reach the end.

222
00:12:17,780 --> 00:12:20,690
That means the current position, the current index.

223
00:12:20,810 --> 00:12:23,420
That means the current position is also a good index.

224
00:12:23,680 --> 00:12:25,690
OK, so this is the main logic.

225
00:12:25,700 --> 00:12:27,120
So I hope you understood the logic.

226
00:12:27,140 --> 00:12:28,400
Now let's write the code.

227
00:12:28,880 --> 00:12:30,720
So writing code is very, very simple.

228
00:12:31,040 --> 00:12:33,000
This will be like four to five lines of code.

229
00:12:33,560 --> 00:12:35,840
So let us first find out the size.

230
00:12:35,870 --> 00:12:37,600
So this is numbers, not size.

231
00:12:37,610 --> 00:12:38,410
And I'm straight size.

232
00:12:38,900 --> 00:12:41,690
OK, so initially, what is the good index?

233
00:12:42,380 --> 00:12:44,720
So last word, let's call it.

234
00:12:46,010 --> 00:12:48,350
OK, so let's call it good position.

235
00:12:52,930 --> 00:12:57,920
So and minus one is the good, because from the last index, I can reach the index.

236
00:12:57,940 --> 00:12:59,020
OK, so what?

237
00:12:59,020 --> 00:13:00,280
The position is in minus one.

238
00:13:01,370 --> 00:13:05,260
Now we have to wait it over the area to ECLSS and minister.

239
00:13:06,180 --> 00:13:07,950
I get it, then I get close to zero.

240
00:13:09,910 --> 00:13:12,310
A minus, minus, OK, simple.

241
00:13:13,320 --> 00:13:20,030
Now, which condition I have to use, so I will use this condition contemplation, platinum's of granulation.

242
00:13:20,040 --> 00:13:23,670
So in our case, I'm using for lupus or what is the current condition?

243
00:13:23,670 --> 00:13:24,100
Is I.

244
00:13:24,380 --> 00:13:24,690
OK.

245
00:13:27,550 --> 00:13:33,660
So if the current position, bless them, makes them jump, that I can take is basically Nimsoft.

246
00:13:34,420 --> 00:13:35,380
So if this thing.

247
00:13:37,000 --> 00:13:38,770
It's basically guerdon articles to.

248
00:13:39,790 --> 00:13:40,750
They go to perdition.

249
00:13:43,040 --> 00:13:45,620
That means the current operation is also going to position.

250
00:13:45,880 --> 00:13:50,090
OK, so the current position is also good position.

251
00:13:50,090 --> 00:13:51,890
So I will update and equal the position.

252
00:13:53,240 --> 00:13:56,520
Now, finally, what we have to do, I have to check for the next zero.

253
00:13:56,730 --> 00:14:03,320
OK, finally what we have to do, I have to check for the index zero weather index zero is a good politician

254
00:14:03,320 --> 00:14:04,280
or a bad position.

255
00:14:06,810 --> 00:14:07,440
Now check.

256
00:14:08,740 --> 00:14:15,580
So if good position is index zero, if basically index zero is a good position, then you will return

257
00:14:15,580 --> 00:14:15,850
to.

258
00:14:17,660 --> 00:14:19,160
Otherwise, you will return false.

259
00:14:21,700 --> 00:14:23,290
OK, so this is the complete gold.

260
00:14:24,690 --> 00:14:27,330
Now, let's first an hour and then we will submit.

261
00:14:30,430 --> 00:14:33,430
OK, so our goal is working fine now let's meet our goal.

262
00:14:34,560 --> 00:14:39,650
Now, what will we do, time in the space complexity of our solution, so it is very simple.

263
00:14:40,290 --> 00:14:46,830
So the time, complexity of our solution is big often and the space complexities big of one.

264
00:14:46,860 --> 00:14:49,080
OK, so this is the time and this is the space.

265
00:14:50,060 --> 00:14:52,040
OK, so this was a very simple question.

266
00:14:53,350 --> 00:15:01,180
OK, if you do not like the name, you can also change it like last a good index and then you can update

267
00:15:01,180 --> 00:15:02,900
the last good index.

268
00:15:02,920 --> 00:15:03,250
OK.

269
00:15:04,830 --> 00:15:10,140
So we are just reversing from the last operation to the first operation, and the idea is basically

270
00:15:10,410 --> 00:15:11,640
if the index is zero.

271
00:15:12,920 --> 00:15:14,750
If Index zero is a good opposition.

272
00:15:15,770 --> 00:15:20,100
If there is a good portion, that means I will be able to reach the last Olympics.

273
00:15:20,120 --> 00:15:25,760
OK, that is the meaning of good word means the index from which you can you can reach the last Hynix.

274
00:15:26,720 --> 00:15:29,470
So if you have any doubt in this question, you can ask me.

275
00:15:29,530 --> 00:15:30,500
OK, thank you.

