1
00:00:00,590 --> 00:00:02,570
Hey there and welcome back!

2
00:00:02,810 --> 00:00:09,500
In the previous videos we have discussed the bottom up or tabulation approach for the list question

3
00:00:09,500 --> 00:00:11,780
using a two dimensional array.

4
00:00:12,080 --> 00:00:18,410
Now let's get started solving this question by just using a one dimensional array.

5
00:00:18,440 --> 00:00:25,820
Now, previously I had mentioned that this can be done because the state of a subproblem can be represented

6
00:00:25,820 --> 00:00:27,440
with just one variable.

7
00:00:27,440 --> 00:00:28,970
So what does this mean?

8
00:00:28,970 --> 00:00:31,280
Let's get started with this.

9
00:00:31,700 --> 00:00:37,610
So we know that in DP problems we need to solve subproblems.

10
00:00:37,610 --> 00:00:44,300
And we need to store those solutions and then use those solutions to come up with the solution to the

11
00:00:44,300 --> 00:00:45,470
original problem.

12
00:00:45,470 --> 00:00:53,120
So we need to store the answer to a subproblem or a particular state of the given problem.

13
00:00:53,120 --> 00:00:54,890
Now for this question.

14
00:00:54,890 --> 00:01:00,020
For the Liz question, the state of the question is one dimensional.

15
00:01:00,020 --> 00:01:06,050
In nature, because we can represent a subproblem with just one variable.

16
00:01:06,050 --> 00:01:07,640
Now what do I mean with this?

17
00:01:07,640 --> 00:01:09,230
Let's take an example.

18
00:01:09,230 --> 00:01:13,400
Let's say the array which is given to us is this array over here.

19
00:01:13,400 --> 00:01:22,010
Now if I have a DP table over here which is one dimensional in nature, and if I have one over one value

20
00:01:22,010 --> 00:01:26,090
over here for every index in the array which is given to me.

21
00:01:26,090 --> 00:01:27,290
So note is over here.

22
00:01:27,290 --> 00:01:29,480
Also I go from 0 to 6.

23
00:01:29,480 --> 00:01:37,640
So if I have an array like this, then I can represent the answers to the subproblems in a way that

24
00:01:37,640 --> 00:01:46,670
dp at index I would represent the longest increasing subsequence, including the element at the ith

25
00:01:46,670 --> 00:01:47,210
index.

26
00:01:47,210 --> 00:01:55,790
So for example, if we talk about dp at three, then it would represent the length of the longest increasing

27
00:01:55,790 --> 00:02:02,300
subsequence for these elements over here in a way that we are also including this element.

28
00:02:02,300 --> 00:02:08,990
So if I have a DP table in this manner, and if I am able to iterate over all the elements of the array

29
00:02:08,990 --> 00:02:16,550
given to me and fill out this DP table, then I would just need to identify which is the greatest value

30
00:02:16,550 --> 00:02:22,250
in the DP table over here, to get the length of the longest increasing subsequence.

31
00:02:22,250 --> 00:02:27,110
Now we will see more of this when we do a dry run of the algorithm.

32
00:02:27,110 --> 00:02:37,610
But over here let's first think how can we identify DP at one if we know the value for dp at zero?

33
00:02:37,610 --> 00:02:44,540
Or in other words, what is the recurrence relation that we can use to iterate over the elements of

34
00:02:44,540 --> 00:02:47,600
the array given to us and fill out this DP table?

35
00:02:47,600 --> 00:02:51,320
So first let's spend some time building this intuition.

36
00:02:51,320 --> 00:02:57,650
And then we will come back and do a dry run of the algorithm and fill this table to understand how this

37
00:02:57,650 --> 00:02:58,100
works.

38
00:02:58,100 --> 00:03:01,880
So over here let's say this is the array which is given to us.

39
00:03:01,880 --> 00:03:04,370
And we have a DP table over here.

40
00:03:04,370 --> 00:03:08,720
So we are trying to build the intuition that we will use to solve this question.

41
00:03:08,720 --> 00:03:17,690
Now I told you that we need to fill the values in this DP table over here such that dp at index I represents

42
00:03:17,690 --> 00:03:18,920
the length.

43
00:03:19,640 --> 00:03:26,180
Of the longest increasing subsequence, where the element at index I.

44
00:03:27,970 --> 00:03:29,320
Is included.

45
00:03:33,830 --> 00:03:37,550
When we take a look at the dry run, we will understand this in depth.

46
00:03:37,550 --> 00:03:40,730
But over here let's just develop the intuition.

47
00:03:40,730 --> 00:03:47,360
So if this is what I want, and if this is the array which is given to me, once I am done filling up

48
00:03:47,360 --> 00:03:53,990
values into this DP table over here, it will look like this 1213345.

49
00:03:53,990 --> 00:03:55,220
Now again, why is this?

50
00:03:55,220 --> 00:03:56,990
So let's try to understand it.

51
00:03:56,990 --> 00:03:59,780
So initially I'm only considering this element.

52
00:03:59,780 --> 00:04:01,280
And that's just one element.

53
00:04:01,280 --> 00:04:02,420
So I have one over here.

54
00:04:02,420 --> 00:04:05,060
Then for this element this is zero.

55
00:04:05,060 --> 00:04:06,020
Sorry this is zero.

56
00:04:06,020 --> 00:04:14,330
This is one this is 2345 and 601234, five and six.

57
00:04:14,330 --> 00:04:20,570
So when I'm trying to fill depee at index one, I can use these values over here.

58
00:04:20,570 --> 00:04:23,090
And I have to include this element.

59
00:04:23,090 --> 00:04:32,180
Now notice that by including this element I can in fact form an increasing subsequence of length two.

60
00:04:32,180 --> 00:04:34,640
And that's why I have two over here.

61
00:04:34,640 --> 00:04:37,490
Now for example, let's take another case.

62
00:04:37,490 --> 00:04:44,810
If I were to consider this element over here, notice that I can form a strictly increasing subsequence

63
00:04:44,810 --> 00:04:48,950
by including this element and including these two elements as well.

64
00:04:48,950 --> 00:04:51,590
So that's why I have the value three over here.

65
00:04:51,590 --> 00:04:57,020
But when it comes to this element over here which is at index two right.

66
00:04:57,020 --> 00:04:58,460
So that's this over here.

67
00:04:58,460 --> 00:05:06,200
So DP at two I need to form a strictly increasing subsequence in which this element is included.

68
00:05:06,200 --> 00:05:13,610
And the only increasing subsequence that I can form by including this element and considering these

69
00:05:13,610 --> 00:05:17,510
possible values is just having this element alone.

70
00:05:17,510 --> 00:05:22,220
So that's why the length of that increasing subsequence is equal to one.

71
00:05:22,220 --> 00:05:25,160
So we have understood what this DP over here is.

72
00:05:25,160 --> 00:05:31,370
Just to summarize over here dp at index I is the length.

73
00:05:32,120 --> 00:05:39,320
Of the longest increasing subsequence, where the element at the ith index is included.

74
00:05:42,070 --> 00:05:45,520
So this is how we will fill the DP table over here.

75
00:05:45,550 --> 00:05:49,120
Now let's quickly discuss one more interesting thing over here.

76
00:05:49,150 --> 00:05:53,290
Notice that for this index that's 0123.

77
00:05:53,590 --> 00:05:54,670
That's this over here.

78
00:05:54,670 --> 00:05:55,540
And this is four.

79
00:05:55,540 --> 00:05:59,050
So this is four over here for DP at index three.

80
00:05:59,140 --> 00:06:03,370
The longest increasing subsequence is 124.

81
00:06:04,480 --> 00:06:10,870
And for DPI at index four, which is this over here I have to include this value.

82
00:06:10,870 --> 00:06:12,010
So I have three over here.

83
00:06:12,010 --> 00:06:15,820
The longest increasing subsequence is one, two, three.

84
00:06:15,850 --> 00:06:20,380
Again I have to include this value and I can consider these elements.

85
00:06:20,380 --> 00:06:27,490
So that's why the longest increasing subsequence is 123 and its length is equal to three.

86
00:06:27,490 --> 00:06:34,990
Now let's also think how would the algorithm identify the length of the longest increasing subsequence

87
00:06:34,990 --> 00:06:40,270
up to the element that we are considering, and including that particular element?

88
00:06:40,270 --> 00:06:45,910
For example, let's say we are trying to find this value over here, and let's say we have already filled

89
00:06:45,910 --> 00:06:48,190
these values in the DP table.

90
00:06:48,190 --> 00:06:54,730
Now, when we are trying to fill this value, what we will do is let's say a pointer is pointing to

91
00:06:54,730 --> 00:07:01,300
this index and we will have another pointer that will go through all the values which are prior to this

92
00:07:01,300 --> 00:07:03,250
in the DP table over here.

93
00:07:03,250 --> 00:07:05,860
So that's these values over here.

94
00:07:05,860 --> 00:07:13,210
And we will see whether the value over here which is four is greater than the value at each respective

95
00:07:13,210 --> 00:07:13,660
place.

96
00:07:13,660 --> 00:07:16,420
So initially we will see that four is greater than one.

97
00:07:17,050 --> 00:07:23,350
Therefore, yes, this is a valid, uh, thing to add to the subsequence, where four is the last element

98
00:07:23,350 --> 00:07:24,580
that is added to it.

99
00:07:24,580 --> 00:07:31,870
And over here we know that the length of the longest increasing subsequence, which includes this element

100
00:07:31,870 --> 00:07:32,590
is one.

101
00:07:32,590 --> 00:07:34,960
Now we come to the next element over here.

102
00:07:34,990 --> 00:07:38,950
See that it's two, and yes, two is less than 4 or 4 is greater than two.

103
00:07:38,950 --> 00:07:45,100
So this also four also could be added to a subsequence where two was the last added element.

104
00:07:45,100 --> 00:07:47,830
And over here we have one four is greater than one.

105
00:07:47,830 --> 00:07:49,480
So all of these are valid.

106
00:07:49,510 --> 00:07:57,130
Now that we have identified the places where we could add four two, we need to identify where to add

107
00:07:57,130 --> 00:08:01,390
it so that we are actually getting the longest increasing subsequence.

108
00:08:01,390 --> 00:08:05,410
So this over here this one over here represents this subsequence.

109
00:08:05,410 --> 00:08:09,610
This two over here represents the subsequence one comma two.

110
00:08:09,610 --> 00:08:13,270
And this one over here represents the subsequence one.

111
00:08:13,270 --> 00:08:18,880
And we have seen that four is greater than the last element in each of these instances.

112
00:08:18,880 --> 00:08:23,290
Now if I were to add four over here, I'll get one comma four.

113
00:08:23,290 --> 00:08:27,910
If I were to add four in this subsequence, I'll get one, two and four.

114
00:08:27,910 --> 00:08:32,620
And if I were to add four to this subsequence, I again get one comma four.

115
00:08:32,620 --> 00:08:40,000
Notice that I get the longest increasing subsequence in this case where depee had the largest value.

116
00:08:40,000 --> 00:08:47,590
So that's why among these I will choose this one and add one to it, and in this way I will get the

117
00:08:47,590 --> 00:08:50,890
value three, which I can fill at this position.

118
00:08:50,890 --> 00:08:54,250
So this is how I can find the value over here.

119
00:08:54,250 --> 00:08:57,790
Now let's see the same thing about this index over here.

120
00:08:57,790 --> 00:08:59,740
So how do I find this value.

121
00:08:59,740 --> 00:09:04,780
Again the subproblem is that we have all these values in the DP table.

122
00:09:05,660 --> 00:09:08,420
And we are trying to find this value over here.

123
00:09:08,420 --> 00:09:14,570
So what we would do is we go and take a look at the value at this index in the array, which is given

124
00:09:14,570 --> 00:09:16,580
to us, which is equal to three.

125
00:09:16,580 --> 00:09:18,380
Again we have the indices right.

126
00:09:18,380 --> 00:09:20,390
So we'll use the indices to find this.

127
00:09:20,390 --> 00:09:21,770
So this is index four.

128
00:09:21,800 --> 00:09:23,210
This is also index four.

129
00:09:23,210 --> 00:09:24,770
So we get the value three.

130
00:09:24,770 --> 00:09:32,270
Now we need another pointer to iterate over all these values and identify all the values which are less

131
00:09:32,270 --> 00:09:32,840
than three.

132
00:09:32,840 --> 00:09:38,330
Or all the cases where the value over here is less than 3 or 3 is greater than the value.

133
00:09:38,330 --> 00:09:39,770
So let's do that.

134
00:09:39,770 --> 00:09:45,710
And we notice that we have values less than three over here, over here and over here.

135
00:09:45,710 --> 00:09:47,660
But over here we have the value four.

136
00:09:47,660 --> 00:09:52,580
So we could not add three to the subsequence that was formed over here.

137
00:09:52,580 --> 00:09:55,310
The longest increasing subsequence including four.

138
00:09:55,310 --> 00:09:57,830
So this is out but these three are in.

139
00:09:57,830 --> 00:10:00,080
So again this subsequence is one.

140
00:10:00,080 --> 00:10:02,630
This is one comma two and this is one.

141
00:10:02,630 --> 00:10:05,600
Now we just need to know where to add three.

142
00:10:05,600 --> 00:10:11,330
And because the largest among these is this we will add one to that value.

143
00:10:11,330 --> 00:10:12,980
And we get three over here.

144
00:10:13,780 --> 00:10:18,130
So this is how we will go ahead and fill the DP table.

145
00:10:18,130 --> 00:10:23,500
But again, over here we are just trying to build an intuition and we are just trying to understand

146
00:10:23,500 --> 00:10:24,430
why this works.

147
00:10:24,430 --> 00:10:30,700
Now we will see this in greater detail in the next video where we will dry run the algorithm filling

148
00:10:30,700 --> 00:10:31,690
the DP table.

149
00:10:31,690 --> 00:10:37,960
Now that we have understood the intuition over here, let's come back to the question that we were discussing,

150
00:10:37,960 --> 00:10:45,430
and let's try to write the recurrence relation that can be used to fill the DP table over here.

151
00:10:45,430 --> 00:10:52,630
So if we know the value for DP at zero, how do we find the next value in the DP table.

152
00:10:52,630 --> 00:10:55,270
So for this we will have two pointers.

153
00:10:55,270 --> 00:10:58,750
Let's say I is pointing to this index over here.

154
00:10:58,750 --> 00:11:05,620
We will need another pointer to go over all the previous values in the array which is given to us,

155
00:11:05,620 --> 00:11:12,070
and we will check whether numb's at I is greater than numb's at j in each index.

156
00:11:12,070 --> 00:11:19,630
And if we see that yes, that's the case, then we will check whether dp at j plus one is greater than

157
00:11:19,630 --> 00:11:20,530
DP at I.

158
00:11:20,530 --> 00:11:24,670
And if that is the case, we would fill that value as dp at I.

159
00:11:24,670 --> 00:11:30,370
And again this would become very clear when we walk through the algorithm and do a dry run.

160
00:11:30,370 --> 00:11:33,460
But over here let's just try to pin it down.

161
00:11:33,460 --> 00:11:39,880
So we will check whether the value over here is greater than the value at index j, and we will check

162
00:11:39,880 --> 00:11:43,330
whether dp at j plus one is greater than dp at I.

163
00:11:43,360 --> 00:11:49,720
Now this part over here is required because earlier remember we had seen that I could add this four

164
00:11:49,720 --> 00:11:51,400
to this sequence over here.

165
00:11:51,400 --> 00:11:53,320
Again over here we had one over here.

166
00:11:53,320 --> 00:11:54,910
We had two over here we had one.

167
00:11:54,910 --> 00:11:57,130
And then over here we had to fill the value.

168
00:11:57,130 --> 00:11:58,750
Remember this over here.

169
00:11:58,750 --> 00:12:00,730
This one represented this sequence.

170
00:12:00,730 --> 00:12:04,960
This two represented one comma two and this one represented one.

171
00:12:04,960 --> 00:12:08,410
So we could add four to either of these sequences.

172
00:12:08,410 --> 00:12:14,380
So that's why we need this part over here to identify which is the correct place to add four.

173
00:12:14,380 --> 00:12:18,490
Or initially you would just go ahead and add four to this subsequence.

174
00:12:18,490 --> 00:12:20,140
So we get one comma four.

175
00:12:20,140 --> 00:12:26,140
But then when we get a better opportunity over here one comma two comma four, we have to change the

176
00:12:26,140 --> 00:12:28,270
value over here to three.

177
00:12:28,300 --> 00:12:32,950
Now again this will become more clear in the next video when we do the dry run.

178
00:12:32,950 --> 00:12:40,720
But if these two conditions are satisfied then we would set DP at I is equal to dp at j plus one, because

179
00:12:40,720 --> 00:12:45,130
we are adding the element at index I to that particular subsequence.

180
00:12:45,130 --> 00:12:49,990
For example, over here the subsequence is one comma two, because of which the length is two.

181
00:12:49,990 --> 00:12:56,410
And when we add dp at I to it, we get one, two and four, and the length over here is two plus one,

182
00:12:56,410 --> 00:12:57,640
which is equal to three.

183
00:12:57,640 --> 00:12:59,920
And that's what this step is for.

184
00:12:59,920 --> 00:13:00,580
All right.

185
00:13:00,580 --> 00:13:08,110
So we have discussed the approach on a high level that we can take to implement the bottom up list solution

186
00:13:08,110 --> 00:13:09,580
with just a 1D array.

187
00:13:09,580 --> 00:13:13,600
And we have also developed an intuition about why this works.

188
00:13:13,600 --> 00:13:16,810
In the next video let's discuss this in detail.

189
00:13:16,810 --> 00:13:19,990
And let's do a dry run to thoroughly understand this.