1
00:00:00,240 --> 00:00:01,350
Welcome back.

2
00:00:01,350 --> 00:00:08,640
We have discussed the memoization approach, which had an O of N into W time and space complexity.

3
00:00:08,640 --> 00:00:15,090
And we have also discussed the tabulation approach, which had a similar time and space complexity,

4
00:00:15,090 --> 00:00:20,670
with the difference that this was an iterative approach and we are not using space on the recursive

5
00:00:20,670 --> 00:00:21,450
call stack.

6
00:00:21,480 --> 00:00:28,800
Now let's go ahead and take a look at how we can optimize the tabulation approach and come up with a

7
00:00:28,800 --> 00:00:30,840
better space complexity for it.

8
00:00:30,840 --> 00:00:34,890
So let's take a look at the space optimized tabulation approach.

9
00:00:34,890 --> 00:00:40,260
So this is the table that we had when we came up with the bottom up approach.

10
00:00:40,260 --> 00:00:46,620
Now let's make some interesting observations over here which will help us to come up with the space

11
00:00:46,620 --> 00:00:48,000
optimized approach.

12
00:00:48,000 --> 00:00:56,310
Notice that whenever we were filling a row, we only needed values that were there in the previous row.

13
00:00:56,460 --> 00:01:04,230
For example, when you were filling this row over here, you only needed the values over here for calculating

14
00:01:04,230 --> 00:01:07,680
the exclude case as well as when you included a value.

15
00:01:07,680 --> 00:01:12,960
You also wanted to understand what extra could be added to the knapsack for both of these.

16
00:01:12,960 --> 00:01:19,290
For calculating the exclude case and the include case, you only needed the previous row.

17
00:01:19,290 --> 00:01:21,090
Now for calculating this.

18
00:01:21,120 --> 00:01:23,730
We never used this nor this.

19
00:01:23,730 --> 00:01:32,970
So this means that we just need to use space for storing the previous row and the current row that we

20
00:01:32,970 --> 00:01:34,140
are computing.

21
00:01:34,140 --> 00:01:39,810
Now let's make use of this insight and optimize the approach that we had taken.

22
00:01:39,810 --> 00:01:46,830
So previously we said that exclude is going to equal to DP at I minus one j and include is going to

23
00:01:46,830 --> 00:01:51,360
equal value at I minus one plus dp at I minus one.

24
00:01:51,360 --> 00:01:55,950
And then whatever the remaining weight that could be added to the knapsack.

25
00:01:55,950 --> 00:02:02,460
Now let's say instead of this DP table we have two 1D arrays.

26
00:02:02,700 --> 00:02:10,740
We can call it previous and cur because we have seen that we just need the previous row to compute the

27
00:02:10,740 --> 00:02:11,430
current row.

28
00:02:11,430 --> 00:02:20,250
Now, instead of dp at I, I will just use the current array and instead of dp at I minus one, I will

29
00:02:20,250 --> 00:02:23,730
just use the previous array which I have over here.

30
00:02:23,730 --> 00:02:27,360
And again the same is applicable over here as well.

31
00:02:28,450 --> 00:02:34,690
And what we will keep doing is like, let's say we are done with computing the values in this array

32
00:02:34,690 --> 00:02:35,230
over here.

33
00:02:35,230 --> 00:02:42,850
So we will set the values over here that were in the current array at this moment to the previous array.

34
00:02:42,850 --> 00:02:47,560
So we will make a copy of this and we will assign it to the previous array.

35
00:02:47,560 --> 00:02:54,430
So in this way we just need to store the previous and current values at a time.

36
00:02:54,430 --> 00:02:59,530
And this would improve the space complexity of the tabulation approach.

37
00:02:59,530 --> 00:03:03,130
Finally the answer is going to be over here.

38
00:03:03,130 --> 00:03:06,010
And that's going to be current at W.

39
00:03:06,010 --> 00:03:11,680
Because again at the end this array over here is going to be there in the current array.

40
00:03:11,680 --> 00:03:16,780
And we just need the last element over here which is going to be current at W.