1
00:00:00,080 --> 00:00:01,070
Welcome back.

2
00:00:01,070 --> 00:00:07,640
So this is the tabulation approach that we had previously written for solving the LCS question.

3
00:00:07,760 --> 00:00:13,010
Now let's go ahead and implement the space optimized tabulation approach.

4
00:00:13,040 --> 00:00:18,290
Now as we have discussed in the previous video, we will not be needing a 2D array.

5
00:00:18,290 --> 00:00:19,880
So let's remove this.

6
00:00:19,880 --> 00:00:26,240
And instead we would need two 1D arrays, each of which is of length m plus one.

7
00:00:26,240 --> 00:00:28,130
So let's go ahead and create them.

8
00:00:28,130 --> 00:00:31,010
So let me call one prev for previous.

9
00:00:31,010 --> 00:00:33,380
And this is going to equal array.

10
00:00:33,380 --> 00:00:36,200
And the size of this is going to be m plus one.

11
00:00:36,200 --> 00:00:40,460
And we will fill every cell in this array initially with the value zero.

12
00:00:40,460 --> 00:00:42,890
And similarly we will need one more array.

13
00:00:42,890 --> 00:00:44,510
So we call it curr.

14
00:00:44,510 --> 00:00:46,910
And this also is going to equal array.

15
00:00:46,910 --> 00:00:48,740
And the size is m plus one.

16
00:00:48,740 --> 00:00:52,640
And we fill every cell in this array with the value zero.

17
00:00:52,670 --> 00:00:53,420
All right.

18
00:00:53,420 --> 00:00:54,530
Now we proceed.

19
00:00:54,530 --> 00:00:58,520
We go ahead and iterate over the cells as we have over here.

20
00:00:58,520 --> 00:00:59,930
And wherever.

21
00:00:59,930 --> 00:01:04,460
Initially we had DP at I, we are going to replace this with curr.

22
00:01:04,460 --> 00:01:09,380
And wherever we have DP at I minus one we are going to change this with prev.

23
00:01:09,380 --> 00:01:11,060
So let's go ahead and do that.

24
00:01:11,060 --> 00:01:13,400
So over here I have DP at I.

25
00:01:13,430 --> 00:01:15,440
So let me replace this with curr.

26
00:01:15,440 --> 00:01:17,570
And over here I have DP at I minus one.

27
00:01:17,570 --> 00:01:19,340
So we write prev over here.

28
00:01:19,610 --> 00:01:21,920
Similarly over here we have DP at I.

29
00:01:21,950 --> 00:01:23,240
So let's write curr.

30
00:01:23,240 --> 00:01:25,760
Over here we have DP at I over here.

31
00:01:26,360 --> 00:01:28,310
So we can write curr over here.

32
00:01:28,310 --> 00:01:30,890
And we have DP at I minus one over here.

33
00:01:30,890 --> 00:01:32,570
So we write prev over here.

34
00:01:32,570 --> 00:01:33,230
All right.

35
00:01:33,230 --> 00:01:34,190
So that's it.

36
00:01:34,190 --> 00:01:37,190
Now there's one more thing that we need to take care over here.

37
00:01:37,220 --> 00:01:42,590
After each row computation or after each value of I is processed okay.

38
00:01:42,590 --> 00:01:48,500
So once we come over here we have to make a copy of the current state of Curr.

39
00:01:48,620 --> 00:01:51,980
And we have to assign it to prev okay.

40
00:01:51,980 --> 00:01:54,980
And then it goes on to the next iteration okay.

41
00:01:54,980 --> 00:01:55,880
So that's it.

42
00:01:55,880 --> 00:02:01,130
And then finally over here we have DP at n and instead of DP at n we write curr.

43
00:02:01,130 --> 00:02:02,750
We have to return curr at n.

44
00:02:02,750 --> 00:02:03,590
So that's it.

45
00:02:03,590 --> 00:02:05,750
So this should take care of this question.

46
00:02:05,750 --> 00:02:10,370
Now let's go ahead and run this code and see if it's passing all the test cases.

47
00:02:11,590 --> 00:02:13,630
And you can see that it's working.

48
00:02:13,630 --> 00:02:15,310
It's passing all the test cases.

49
00:02:15,310 --> 00:02:21,880
So this is the way that we can solve the LCS question using the space optimized tabulation approach.