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.