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.

