1
00:00:00,970 --> 00:00:02,140
Welcome back.

2
00:00:02,140 --> 00:00:08,680
In the previous video, we have seen how we can memorize the recursive approach and we were able to

3
00:00:08,680 --> 00:00:16,030
achieve a much better time complexity, which was of the order of n squared as compared with the recursive

4
00:00:16,030 --> 00:00:19,870
approach, which had a time complexity of the order of two to the power n.

5
00:00:19,870 --> 00:00:25,810
Now let's discuss the bottom up or tabulation approach for solving the list question.

6
00:00:25,810 --> 00:00:28,540
Now we can do this in two ways.

7
00:00:28,540 --> 00:00:32,350
That is, using a 2D array or a 1D array.

8
00:00:32,350 --> 00:00:36,700
So we will first discuss the approach where we are using a 2D array.

9
00:00:36,700 --> 00:00:44,740
But also remember we can solve this question using a 1D array, because the state of the problem can

10
00:00:44,740 --> 00:00:47,950
be represented with just one variable.

11
00:00:47,950 --> 00:00:56,800
Or in other words, if we have an array, we can use just this one index over here to identify the answer

12
00:00:56,800 --> 00:00:57,670
to a subproblem.

13
00:00:57,670 --> 00:01:03,370
Or like for example, if we have three elements, then we have zero, one and two as the indices.

14
00:01:03,370 --> 00:01:10,390
Now probably there is a way in which we can identify the alias for this subproblem.

15
00:01:10,390 --> 00:01:13,750
Then we can identify the alias for this subproblem.

16
00:01:13,750 --> 00:01:15,340
Using this subproblem.

17
00:01:15,340 --> 00:01:20,980
And in a similar manner, we can use the solution to this subproblem for finding the alias where we

18
00:01:20,980 --> 00:01:23,050
are considering this complete array.

19
00:01:23,170 --> 00:01:30,550
So this indicates that probably we can just use a one dimensional DP array for solving this as well.

20
00:01:30,550 --> 00:01:32,680
But more of that in a future video.

21
00:01:32,680 --> 00:01:39,940
Now let's get started with the 2D version of the bottom up or tabulation approach for solving the alias

22
00:01:39,940 --> 00:01:40,570
question.

23
00:01:41,260 --> 00:01:48,100
Now to discuss this approach, let's take again an example where the array which is given to us is one,

24
00:01:48,100 --> 00:01:48,820
two, three.

25
00:01:48,820 --> 00:01:52,000
And over here n is three because we have three elements.

26
00:01:52,000 --> 00:01:56,590
Now let me write the indices over here zero, one and two.

27
00:01:56,620 --> 00:02:04,060
Now we have seen that in the recursive approach there were two parameters that had to be passed to every

28
00:02:04,060 --> 00:02:10,510
call to the alias function, which were the current index and the previous index which was included

29
00:02:10,510 --> 00:02:13,300
lastly in the subsequence at hand.

30
00:02:13,300 --> 00:02:19,480
So the value we have discussed for the current index ranges from 0 to 2.

31
00:02:20,690 --> 00:02:28,910
Or zero to n minus one, and the values for the previous index in this case would range from minus one

32
00:02:28,910 --> 00:02:36,230
up to one, and minus one indicates that no value has been added to the subsequent so far, and it's

33
00:02:36,230 --> 00:02:42,500
only going up to one because the previous index has to be lower than the current index, and the largest

34
00:02:42,500 --> 00:02:44,540
value for the current index is two.

35
00:02:44,570 --> 00:02:48,230
So that's why the previous index only goes up to one.

36
00:02:48,230 --> 00:02:52,520
Now, as we've discussed in the memoization approach over here.

37
00:02:52,520 --> 00:03:00,800
Also, we need to offset the values of the previous index over here by one so that we are able to represent

38
00:03:00,800 --> 00:03:02,630
this in a 2D array.

39
00:03:02,630 --> 00:03:04,700
Because over here we have a negative value.

40
00:03:04,700 --> 00:03:09,170
And that's not conducive for representing this in a 2D DP array.

41
00:03:09,170 --> 00:03:11,690
So let's offset these values by one.

42
00:03:11,690 --> 00:03:16,370
So minus one becomes zero zero becomes one and one becomes two.

43
00:03:16,400 --> 00:03:23,990
So over here now we can use this 2D table to come up with the bottom up or tabulation approach.

44
00:03:23,990 --> 00:03:26,960
For the last question let's call this DP.

45
00:03:27,500 --> 00:03:30,530
So we have DP over here which is a 2D array.

46
00:03:30,560 --> 00:03:34,250
Now previous takes the values from -1 to 1.

47
00:03:34,250 --> 00:03:38,120
But we have offset these values to zero one and two.

48
00:03:38,150 --> 00:03:40,580
So that's these three indices over here.

49
00:03:40,940 --> 00:03:43,760
So zero indicates prev is equal to minus one.

50
00:03:43,760 --> 00:03:48,320
One indicates prev is equal to zero and two indicates prev is equal to one.

51
00:03:48,320 --> 00:03:51,560
Now current takes the values from 0 to 2.

52
00:03:51,590 --> 00:03:56,930
So we have zero one and two which are the values that current takes in this table.

53
00:03:56,930 --> 00:04:00,620
Now what would a cell in this table indicate.

54
00:04:00,620 --> 00:04:02,180
Let's try to think about that.

55
00:04:02,180 --> 00:04:05,510
For example let's take this cell over here.

56
00:04:05,510 --> 00:04:15,200
Now this cell over here gives the longest increasing subsequence that can include values at index two

57
00:04:15,200 --> 00:04:17,480
or to the right of two.

58
00:04:17,510 --> 00:04:23,450
That means it can include values starting at index two and to the right of it.

59
00:04:23,450 --> 00:04:28,250
If there were more elements over here, we could include them as well if possible.

60
00:04:28,250 --> 00:04:37,850
So the row value over here gives us the index of the first element that can be considered for this subproblem

61
00:04:37,850 --> 00:04:40,100
to be included in the subsequence.

62
00:04:40,100 --> 00:04:46,610
And then we can include all the elements to the right of it or greater than this index over here.

63
00:04:46,610 --> 00:04:51,350
So that's what the row value in this DP table specifies.

64
00:04:51,350 --> 00:04:53,210
And what about the column value.

65
00:04:53,210 --> 00:04:58,220
So for this subproblem this subproblem over here the column value is one.

66
00:04:58,220 --> 00:05:05,660
And we know that if this is one it indicates that prev is one minus one which is equal to zero.

67
00:05:05,660 --> 00:05:13,460
So for this subproblem the value of prev is equal to zero, which indicates that any value to be included

68
00:05:13,460 --> 00:05:19,820
in the subsequence, or in the longest increasing subsequence that is represented by this cell.

69
00:05:19,820 --> 00:05:27,140
The value has to be greater than the value at index, prev or in this case index zero.

70
00:05:27,140 --> 00:05:30,080
So over here at index zero, we have the value one.

71
00:05:30,080 --> 00:05:37,370
So any value that is included in this subsequence represented by this cell has to be greater than this

72
00:05:37,370 --> 00:05:38,330
value over here.

73
00:05:38,330 --> 00:05:44,690
But again remember we cannot include this value only values starting at index two which is.

74
00:05:44,690 --> 00:05:50,360
This index over here can be added to this subproblems subsequence.

75
00:05:50,360 --> 00:05:53,300
We will soon see how to fill this table over here.

76
00:05:53,300 --> 00:05:59,240
But because we have defined this subproblem, notice that the value that comes over here is going to

77
00:05:59,240 --> 00:06:06,320
be equal to one, because we can only take elements starting over here, which is we just have three

78
00:06:06,320 --> 00:06:07,130
to consider.

79
00:06:07,130 --> 00:06:12,500
And we can include three to the subsequence because three is greater than one.

80
00:06:12,500 --> 00:06:18,950
This one over here is this one which is the value at the previous index which is equal to zero.

81
00:06:18,950 --> 00:06:20,750
So over here we would fill one.

82
00:06:20,750 --> 00:06:22,250
But more of that later.

83
00:06:22,250 --> 00:06:29,630
We have seen and understood the definition of the row and column for this 2D depee table.

84
00:06:29,630 --> 00:06:38,000
Now before we have a dry run of filling this table, let's just play around with it a bit to solidify

85
00:06:38,000 --> 00:06:39,200
our learning.

86
00:06:39,200 --> 00:06:43,550
So this problem over here, can you tell me what it represents.

87
00:06:43,550 --> 00:06:48,950
It represents that we can include values starting at index zero.

88
00:06:48,950 --> 00:06:55,640
Because car is equal to zero and prev is equal to minus one, which indicates that as of now nothing

89
00:06:55,640 --> 00:06:57,560
has been added to the subsequence.

90
00:06:57,560 --> 00:07:02,120
So the values that we can include are one, two, three.

91
00:07:02,120 --> 00:07:09,170
And there is no condition to be kept in mind when we start considering to include the first value over

92
00:07:09,170 --> 00:07:12,110
here, because nothing has been added so far.

93
00:07:12,110 --> 00:07:13,910
What about this cell over here?

94
00:07:13,940 --> 00:07:18,110
This cell represents values starting at index one.

95
00:07:18,110 --> 00:07:20,120
So we can only consider two.

96
00:07:20,120 --> 00:07:20,240
And.

97
00:07:20,430 --> 00:07:26,160
Three to be included to the subsequence, but prev is still minus one, so nothing has been added to

98
00:07:26,160 --> 00:07:26,940
the subsequence.

99
00:07:26,940 --> 00:07:31,890
So there is no problem in including this element because as of now nothing has been added.

100
00:07:31,920 --> 00:07:37,500
In a similar manner, this cell over here considers only the element three and nothing has been added

101
00:07:37,500 --> 00:07:38,730
to the subsequence.

102
00:07:38,760 --> 00:07:45,840
Now, when it comes to this cell, notice that this over here is not meaningful because prev has to

103
00:07:45,840 --> 00:07:47,970
be lower than the current value.

104
00:07:47,970 --> 00:07:50,100
So we will not be filling this value.

105
00:07:50,100 --> 00:07:55,560
And when it comes to this cell over here we can take elements starting at index one.

106
00:07:55,560 --> 00:07:59,370
So over here also we have two comma three for consideration.

107
00:07:59,370 --> 00:08:04,440
But the values have to be greater than the value at index zero.

108
00:08:04,440 --> 00:08:06,450
And in this case that's equal to one.

109
00:08:06,450 --> 00:08:08,610
So that's why we have greater than one over here.

110
00:08:08,850 --> 00:08:10,650
What about this subproblem.

111
00:08:10,650 --> 00:08:15,540
In this subproblem again we will only consider values starting at index two.

112
00:08:15,540 --> 00:08:18,120
And that's just this one element three.

113
00:08:18,120 --> 00:08:24,900
But the values whatever is to be included in a subsequence has to be greater than one, because that's

114
00:08:24,900 --> 00:08:27,090
the value at this index over here.

115
00:08:27,640 --> 00:08:30,670
All right, now, what about this cell over here again?

116
00:08:30,670 --> 00:08:32,110
This cell has prev.

117
00:08:32,140 --> 00:08:33,400
Greater than cur.

118
00:08:33,400 --> 00:08:35,620
So this is not meaningful.

119
00:08:35,620 --> 00:08:37,150
And we will not be filling it.

120
00:08:37,150 --> 00:08:42,100
And over here also notice that prev is equal to one and cur is equal to one.

121
00:08:42,100 --> 00:08:43,390
They can't be equal.

122
00:08:43,390 --> 00:08:45,610
Prev has to be smaller than cur.

123
00:08:45,610 --> 00:08:47,860
So this also will not be filled.

124
00:08:47,860 --> 00:08:49,450
And then we come over here.

125
00:08:49,450 --> 00:08:50,980
Over here cur is equal to two.

126
00:08:51,010 --> 00:08:54,850
So we can consider elements starting at index two.

127
00:08:54,850 --> 00:08:58,210
And because the array over here has just three elements.

128
00:08:58,210 --> 00:09:00,700
So we only have one element over here.

129
00:09:00,700 --> 00:09:03,400
And prev over here is equal to one.

130
00:09:03,400 --> 00:09:11,290
So if we decide to include an element for this subproblem it has to have a value greater than two which

131
00:09:11,290 --> 00:09:15,580
is the value at this index over here that's this prev which has a value two.

132
00:09:15,580 --> 00:09:21,640
So whatever is to be included in this subproblems subsequence has to have a value greater than two.

133
00:09:21,670 --> 00:09:24,730
So this is how we will fill this 2D dp array.

134
00:09:24,730 --> 00:09:27,340
And then there is no cur equal to three.

135
00:09:27,340 --> 00:09:29,770
Notice over here the last valid index is two.

136
00:09:29,800 --> 00:09:32,980
So all of this has to be filled with zero right.

137
00:09:33,700 --> 00:09:39,130
Because again when we wrote the recursive solution remember we had written that if cur is greater than

138
00:09:39,130 --> 00:09:40,840
n minus one return zero.

139
00:09:40,840 --> 00:09:42,400
So that's this zero over here.

140
00:09:42,490 --> 00:09:48,010
Again remember in a previous video we had discussed writing the recursive solution will help us identify

141
00:09:48,010 --> 00:09:51,040
the initial conditions for the tabulation approach.

142
00:09:51,040 --> 00:09:56,680
And over here also we can just fill it with zero because there is no prev equal to three.

143
00:09:56,680 --> 00:10:01,870
And again we will not be using this, but we can fill over here also the values zero.

144
00:10:01,870 --> 00:10:05,650
So these are the initial conditions for the 2D depee table.

145
00:10:05,650 --> 00:10:13,210
And once we are done filling this table can you tell me where will the answer to the problem be?

146
00:10:13,330 --> 00:10:17,800
Or at which cell will the answer to the problem be located?

147
00:10:17,800 --> 00:10:20,470
Yes, you are right, it's going to be over here.

148
00:10:20,470 --> 00:10:24,010
So this cell over here will give us the answer.

149
00:10:24,010 --> 00:10:28,990
Because again notice this subproblem means that nothing has been added so far.

150
00:10:28,990 --> 00:10:36,280
And you can consider adding elements starting from index zero of the array which is given to us.

151
00:10:36,280 --> 00:10:40,660
So notice that that is the original problem which was given to us.

152
00:10:40,660 --> 00:10:45,970
So once we are able to fill this cell, we will get the answer to the problem at hand.

153
00:10:46,450 --> 00:10:49,150
So first we will fill this cell.

154
00:10:49,150 --> 00:10:50,710
Then we will fill this one.

155
00:10:50,710 --> 00:10:52,180
Then we will fill this one.

156
00:10:52,180 --> 00:10:55,150
And then in a similar manner we will fill these cells.

157
00:10:55,150 --> 00:10:59,890
And finally we will come to this cell and find the answer to the question.

158
00:10:59,890 --> 00:11:01,510
Now a quick side note.

159
00:11:01,510 --> 00:11:04,690
Remember we did the same thing in recursion.

160
00:11:04,690 --> 00:11:11,860
And that's why writing the recursive function before going for the tabulation approach or the bottom

161
00:11:11,860 --> 00:11:14,230
up approach is quite helpful.

162
00:11:14,230 --> 00:11:21,460
So notice over here in a previous slide we had said that las at curr and prev will return the longest

163
00:11:21,460 --> 00:11:28,270
increasing subsequence starting at index curve to the right of it of the array which is given to us.

164
00:11:28,270 --> 00:11:34,300
And that's what we've just now discussed about the row value for the 2D depee table.

165
00:11:34,300 --> 00:11:34,900
Right.

166
00:11:34,900 --> 00:11:39,670
So we have done the same thing when we were discussing recursion as well.

167
00:11:40,830 --> 00:11:47,400
And over here notice that it's mentioned values have to be greater than the value at index equal to

168
00:11:47,400 --> 00:11:47,760
prev.

169
00:11:47,760 --> 00:11:49,110
And we had prev over here.

170
00:11:49,110 --> 00:11:53,820
And that's the condition that we have discussed for the 2D table as well.

171
00:11:53,820 --> 00:11:56,880
So we have prev in the column value.

172
00:11:56,880 --> 00:12:04,410
So whenever we are trying to fill a particular cell we can start with values at this index over here

173
00:12:04,410 --> 00:12:05,730
which is given over here.

174
00:12:05,730 --> 00:12:12,990
And whatever value is to be included in the subsequence that will give the answer to this cell has to

175
00:12:12,990 --> 00:12:18,390
have a value greater than the value at index prev in the array which is given to us.

176
00:12:18,390 --> 00:12:23,100
So that's the same thing that we did when we discussed the recursive solution as well.