1 00:00:01,110 --> 00:00:02,050 Hello, everyone. 2 00:00:02,250 --> 00:00:07,860 So in this video, we'll be writing the code for the unique problem as discussed in our last video. 3 00:00:08,130 --> 00:00:10,950 So what is America's evolution? 4 00:00:11,580 --> 00:00:12,600 It is very simple. 5 00:00:12,600 --> 00:00:15,330 DPF idea will be deep off. 6 00:00:15,900 --> 00:00:22,610 I might some Komachi plus deep off I and J minus one. 7 00:00:22,830 --> 00:00:24,150 And what will be our answer? 8 00:00:24,420 --> 00:00:28,350 Our answer will be DPF M minus one and and minus one. 9 00:00:28,590 --> 00:00:30,660 And what is 80 present. 10 00:00:31,710 --> 00:00:32,490 What DPF. 11 00:00:32,490 --> 00:00:39,360 I do represent it represent Namaroff unique possible part to reach index icon magic. 12 00:00:40,290 --> 00:00:41,820 And this will be our answer. 13 00:00:42,390 --> 00:00:45,810 Simple right now let's start writing the code for this problem. 14 00:00:49,820 --> 00:00:51,700 So they need to do we need to create one. 15 00:00:52,790 --> 00:00:56,690 So let's create a debris Amaru's. 16 00:00:57,830 --> 00:00:58,580 And Gollum's. 17 00:01:00,780 --> 00:01:02,820 Now, what we need to do so. 18 00:01:04,200 --> 00:01:09,590 Let's discuss what will be the best case to see if this is your deputy. 19 00:01:11,770 --> 00:01:18,670 Or let's say this is your McCrossin grid, if you want to reach this is your starting, if you want 20 00:01:18,670 --> 00:01:25,460 to reach this index or this index or this index or this index, how many possible ways will be there? 21 00:01:25,750 --> 00:01:32,680 So the answer is when there's only one unique possible path to reach index, this one, this one, this 22 00:01:32,680 --> 00:01:33,550 one or this one. 23 00:01:33,550 --> 00:01:33,810 Why? 24 00:01:34,000 --> 00:01:36,730 Because you can only move in the right direction. 25 00:01:37,060 --> 00:01:40,990 So far, reaching this particular index, what do you do? 26 00:01:41,140 --> 00:01:42,840 You will move in this direction only. 27 00:01:43,180 --> 00:01:45,040 So there will be only one unique path. 28 00:01:45,280 --> 00:01:48,900 Similarly for this index, you can only move in this direction. 29 00:01:49,240 --> 00:01:52,360 So there is only one unique index, one unique battery. 30 00:01:52,750 --> 00:01:56,220 And similarly for this index, you can move only in this direction. 31 00:01:56,470 --> 00:01:58,380 So there will be only one unique part. 32 00:01:58,840 --> 00:02:02,820 And similarly for this, you will move in this direction. 33 00:02:02,830 --> 00:02:04,280 So there will be one unique path. 34 00:02:04,630 --> 00:02:08,620 So basically you're depressed how your depression look like. 35 00:02:12,120 --> 00:02:13,680 So all these values. 36 00:02:17,440 --> 00:02:19,480 So all these values will be one. 37 00:02:24,460 --> 00:02:31,090 Right, you are you are standing here, and if you want to reach any of this, it makes the only possible 38 00:02:31,090 --> 00:02:32,640 way is you will move down. 39 00:02:33,040 --> 00:02:38,800 So there is only one unique possible path, similarly to reach any of these indexes. 40 00:02:38,980 --> 00:02:44,650 The only possible ways you will move in the right hand side and this and that will be only one unique 41 00:02:44,650 --> 00:02:44,980 part. 42 00:02:45,460 --> 00:02:45,930 Right. 43 00:02:46,420 --> 00:02:55,630 So we will initialize our deprave with all the ones in the first column and basically all the one in 44 00:02:55,630 --> 00:02:56,260 the first row. 45 00:02:56,290 --> 00:02:58,800 So this is first row and this is first column. 46 00:02:58,990 --> 00:03:02,110 So basically zero through and as you read column. 47 00:03:02,120 --> 00:03:05,030 So we need to initialize with all the ones here and all the ones here. 48 00:03:05,680 --> 00:03:06,730 So let's do that. 49 00:03:16,520 --> 00:03:27,050 So let's start writing the code, so what we need to do, let's initialize our DP at the best case. 50 00:03:31,220 --> 00:03:37,520 So I equals zero, I then am I plus plus. 51 00:03:40,480 --> 00:03:42,430 DP of I. 52 00:03:44,890 --> 00:03:46,450 And zero will be when. 53 00:03:48,770 --> 00:03:50,270 Similarly, we will do the same. 54 00:03:52,650 --> 00:03:55,610 So and let's take J. 55 00:03:55,610 --> 00:04:00,960 J equals zero G and then and G plus plus. 56 00:04:02,720 --> 00:04:13,610 And BP of Zero and G will be one fine now our best guess is right now what we need to do, we need to 57 00:04:13,610 --> 00:04:16,430 utilize this reconciliation. 58 00:04:16,970 --> 00:04:19,820 So let's do that. 59 00:04:19,820 --> 00:04:21,010 Let's fill our Deepti. 60 00:04:21,019 --> 00:04:24,860 So I would start from when obviously I lost then. 61 00:04:25,160 --> 00:04:26,780 Am I placeless? 62 00:04:28,860 --> 00:04:39,270 Now for column so J equals one J less than N j plus plus and what will be our DP of IJI? 63 00:04:40,320 --> 00:04:45,750 So DP of IJA will be nothing but DP of a minus one plus G. 64 00:04:52,370 --> 00:05:02,840 Plus, deep of I and J minus one, and finally, when we come out of the for loop, our DPRK will be 65 00:05:02,840 --> 00:05:10,370 completely filled and our answer will be DPE of M minus one and and minus one. 66 00:05:14,890 --> 00:05:19,280 That's so simple, gold, and this is the entire gold. 67 00:05:19,630 --> 00:05:22,030 Now let's celebrate our gold. 68 00:05:28,550 --> 00:05:30,890 So basically, our goal is working fine. 69 00:05:33,010 --> 00:05:39,880 So our goal past all the test cases now let's discuss what is the time, complexity and the space complexity 70 00:05:39,880 --> 00:05:45,220 for this problem so that time complexity is basically big off M Cross. 71 00:05:45,220 --> 00:05:47,160 And and what is the space? 72 00:05:47,170 --> 00:05:47,890 Complexity? 73 00:05:48,040 --> 00:05:53,970 Space complexity is also M Cross and you are creating a deep of size across. 74 00:05:53,970 --> 00:05:55,750 And so that is your space complexity. 75 00:05:56,080 --> 00:06:00,220 And basically this loop is contributing towards your time complexity. 76 00:06:00,820 --> 00:06:08,740 So now the challenge is basically what I have seen is one of my friend was given this question in an 77 00:06:08,740 --> 00:06:11,800 interview, so he solved the problem using this approach. 78 00:06:12,070 --> 00:06:14,250 But the interviewer asked him, can you do better? 79 00:06:14,710 --> 00:06:17,020 Can you reduce time or space complexity? 80 00:06:17,260 --> 00:06:23,050 So your challenges, can you reduce the time, complexity and space complexity for this problem? 81 00:06:24,570 --> 00:06:29,190 So I will discuss the solution, I will discuss this next with you, but you should give it a try. 82 00:06:30,060 --> 00:06:30,750 Give it a try. 83 00:06:30,780 --> 00:06:36,240 You will be able to reduce the time and the space complexity answer is basically you need to use maths 84 00:06:37,200 --> 00:06:39,870 and maths yesterday about permutation combination. 85 00:06:40,170 --> 00:06:44,670 So we will we are going to use that logic only to reduce the time and space complexity. 86 00:06:45,830 --> 00:06:52,010 So try to do this yourself, and if you are not able to do this yourself, then watch the next video. 87 00:06:52,400 --> 00:06:55,080 OK, so I will see you in the next one. 88 00:06:55,280 --> 00:06:55,820 Bye bye.