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

2
00:00:01,350 --> 00:00:04,200
Let's try to understand how we can solve this question.

3
00:00:04,200 --> 00:00:05,520
Let's take an example.

4
00:00:05,520 --> 00:00:09,900
So we have five six for division addition one and subtraction.

5
00:00:09,900 --> 00:00:12,540
Now we can solve this question using a stack.

6
00:00:12,540 --> 00:00:17,850
Because the interesting thing is that we always need the latest two numbers when we are encountering

7
00:00:17,850 --> 00:00:18,480
an operator.

8
00:00:18,480 --> 00:00:18,720
Right.

9
00:00:18,720 --> 00:00:23,040
So to get this done, to get this solved we can use a stack.

10
00:00:23,040 --> 00:00:24,870
So let's try to see how we can use this.

11
00:00:24,870 --> 00:00:27,120
So initially the stack is empty.

12
00:00:27,120 --> 00:00:30,240
And I'm just implementing the stack over here as an array.

13
00:00:30,240 --> 00:00:33,870
And we are going to traverse the given array which is this array over here.

14
00:00:33,870 --> 00:00:35,250
Let's just call it tokens.

15
00:00:35,250 --> 00:00:38,400
So we're going to traverse the tokens array from left to right.

16
00:00:38,400 --> 00:00:43,560
So whenever we are going to encounter an integer for example over here we have five.

17
00:00:43,560 --> 00:00:45,390
We will just push it to our stack.

18
00:00:45,390 --> 00:00:46,830
So we push five.

19
00:00:46,830 --> 00:00:47,730
Then we get six.

20
00:00:47,730 --> 00:00:48,660
So we push six.

21
00:00:48,660 --> 00:00:49,560
Then we get four.

22
00:00:49,560 --> 00:00:51,750
So we push four also into our stack.

23
00:00:51,750 --> 00:00:54,930
Now we are going to encounter an operator right.

24
00:00:54,930 --> 00:00:56,010
So which is division.

25
00:00:56,010 --> 00:01:01,980
So when we are encountering an operator what we will do is we will have to get the two previous numbers.

26
00:01:01,980 --> 00:01:05,550
So let's have two variables number one and number two.

27
00:01:05,550 --> 00:01:08,010
And then we will just do stack dot pop right.

28
00:01:08,010 --> 00:01:11,040
So we're going to pop out of the stack or remove from the end.

29
00:01:11,040 --> 00:01:13,410
So first we are going to get this four over here.

30
00:01:13,410 --> 00:01:18,180
But again remember the way we are going to operate this is it should be six divided by four.

31
00:01:18,180 --> 00:01:22,860
So whatever we are going to get first when we are popping this will be number two.

32
00:01:22,860 --> 00:01:26,670
So we are going to pop and we get number two and we assign it to number two.

33
00:01:26,700 --> 00:01:28,020
So four is number two.

34
00:01:28,020 --> 00:01:30,540
And then we are going to again pop from the stack.

35
00:01:30,540 --> 00:01:32,790
And we're going to assign that to number one.

36
00:01:32,790 --> 00:01:34,470
So number one is equal to six.

37
00:01:34,470 --> 00:01:36,450
And number two is equal to four.

38
00:01:36,450 --> 00:01:39,300
Now we will just do the operation which is division.

39
00:01:39,300 --> 00:01:41,910
So we go ahead and do six divided by four.

40
00:01:41,940 --> 00:01:43,650
That's equal to 1.5.

41
00:01:43,650 --> 00:01:48,150
And then because in the question it's mentioned that in the case of division we have to truncate towards

42
00:01:48,150 --> 00:01:48,540
zero.

43
00:01:48,540 --> 00:01:50,760
So 1.5 becomes one.

44
00:01:51,540 --> 00:01:51,930
All right.

45
00:01:51,930 --> 00:01:55,080
Now, once we get this one over here again, it's an integer.

46
00:01:55,080 --> 00:01:57,180
So we have to push it to our stack.

47
00:01:57,180 --> 00:01:59,340
So we push this one to our stack.

48
00:01:59,340 --> 00:01:59,730
All right.

49
00:01:59,730 --> 00:02:01,050
So we get one over here.

50
00:02:01,050 --> 00:02:05,100
And then we are going to continue traversing the I the array over here.

51
00:02:05,100 --> 00:02:06,060
So we move ahead.

52
00:02:06,060 --> 00:02:10,830
And after this we can see that this is how our stack looks like at this moment.

53
00:02:10,830 --> 00:02:13,680
So we move ahead and over here we get plus.

54
00:02:13,680 --> 00:02:14,100
All right.

55
00:02:14,100 --> 00:02:15,420
So we again get plus.

56
00:02:15,420 --> 00:02:16,560
So that's an operator.

57
00:02:16,560 --> 00:02:19,440
So we have to identify the previous two numbers.

58
00:02:19,440 --> 00:02:21,600
So we are just going to pop from the stack.

59
00:02:21,600 --> 00:02:24,270
And what are we going to get first is going to be number two.

60
00:02:24,300 --> 00:02:25,800
So number two is one.

61
00:02:25,800 --> 00:02:27,150
And then we pop again.

62
00:02:27,150 --> 00:02:29,250
And that's going to be equal to number one.

63
00:02:29,250 --> 00:02:30,900
So we got five and one.

64
00:02:30,900 --> 00:02:32,580
And then we'll just do the operation.

65
00:02:32,580 --> 00:02:35,160
So five plus one is equal to six.

66
00:02:35,160 --> 00:02:36,570
And this is an integer.

67
00:02:36,570 --> 00:02:39,030
And we have to push this back to our stack.

68
00:02:39,030 --> 00:02:41,040
So we get six again in our stack.

69
00:02:41,040 --> 00:02:42,300
And then we move ahead.

70
00:02:42,300 --> 00:02:44,640
And you can see the stack looks like this.

71
00:02:44,640 --> 00:02:48,180
At the moment we move ahead and we get one over here it's an integer.

72
00:02:48,180 --> 00:02:49,920
So we push it to our stack.

73
00:02:49,920 --> 00:02:53,220
Again we proceed and we get minus which is an operator.

74
00:02:53,220 --> 00:02:55,740
Therefore again we have to identify number one.

75
00:02:55,740 --> 00:02:56,460
And number two.

76
00:02:56,460 --> 00:02:58,470
For this we're going to pop from the stack.

77
00:02:58,470 --> 00:03:01,350
Whatever we are getting first is going to be equal to number two.

78
00:03:01,380 --> 00:03:02,910
So number two is equal to one.

79
00:03:02,910 --> 00:03:05,100
And number one is going to be equal to six.

80
00:03:05,100 --> 00:03:07,320
Again we pop from the stack to get six.

81
00:03:07,320 --> 00:03:08,850
Now we're going to do the operation.

82
00:03:08,850 --> 00:03:11,610
So six minus one that's equal to five.

83
00:03:11,610 --> 00:03:13,290
And again this is an integer.

84
00:03:13,290 --> 00:03:15,150
So we push it back to our stack.

85
00:03:15,150 --> 00:03:17,190
So we get five in our stack.

86
00:03:17,190 --> 00:03:19,470
And then we have completed going through the array.

87
00:03:19,470 --> 00:03:19,740
Right.

88
00:03:19,740 --> 00:03:25,800
So after iterating through the array whatever is the integer that is there in the stack at the end.

89
00:03:25,800 --> 00:03:26,160
Right.

90
00:03:26,160 --> 00:03:29,910
The last element in the stack, that's going to be our answer.

91
00:03:29,910 --> 00:03:32,520
And we can just return this five over here.

92
00:03:32,520 --> 00:03:34,170
So we will just return five.

93
00:03:34,170 --> 00:03:36,750
And that is how we will solve this question.

94
00:03:36,750 --> 00:03:40,950
Now let's take a quick look at the space and time complexity of this solution.

95
00:03:40,950 --> 00:03:44,190
Now you can see that we have to iterate through the array right.

96
00:03:44,190 --> 00:03:46,860
So we have to move traverse the array which is given to us.

97
00:03:46,860 --> 00:03:49,740
So let's say the array has n elements.

98
00:03:49,740 --> 00:03:55,710
In that case we can say the time complexity is o of n again in each of these instances.

99
00:03:55,710 --> 00:03:58,530
So again first let me just write it down over here.

100
00:03:58,530 --> 00:04:00,240
So we are traversing the array.

101
00:04:00,240 --> 00:04:03,060
So that's why the time complexity is O of n.

102
00:04:03,060 --> 00:04:08,700
And also notice that in each of these instances when we are traversing the array we are just checking

103
00:04:08,700 --> 00:04:13,230
if something is there in somewhere, like if it's an operator or if it's an integer.

104
00:04:13,230 --> 00:04:14,520
So we will do that check.

105
00:04:14,520 --> 00:04:17,760
And then if it's an integer, we will push to the stack.

106
00:04:17,760 --> 00:04:21,240
If it's an operator, then we are popping from the stack and doing some operations.

107
00:04:21,240 --> 00:04:24,450
So you can see that all of that is just constant time operations.

108
00:04:24,450 --> 00:04:24,750
Right.

109
00:04:24,750 --> 00:04:28,290
So that's why the time complexity is just O of N.

110
00:04:28,290 --> 00:04:30,540
And what about the space complexity?

111
00:04:30,540 --> 00:04:33,390
Again Big-O analysis gives us an upper bound.

112
00:04:33,390 --> 00:04:37,920
And we know that we are consuming extra space because we have this stack over here.

113
00:04:37,920 --> 00:04:41,970
Now, even though the stack will not have all the n elements at a time.

114
00:04:41,970 --> 00:04:45,630
But still, we can say that it's not going to be more than n, right?

115
00:04:45,630 --> 00:04:48,660
So again, it's not constant space because it will depend, right?

116
00:04:48,660 --> 00:04:55,050
For example, if it's something like this 567813 and then it goes on for a long time, and then the

117
00:04:55,050 --> 00:04:56,160
first operator comes.

118
00:04:56,160 --> 00:04:58,320
So you can say it's not constant space, right.

119
00:04:58,320 --> 00:05:01,380
So it will have all these elements at a time in the stack.

120
00:05:01,380 --> 00:05:06,840
So we can say that the upper bound of the stack of or the space that we are consuming over here is equal

121
00:05:06,840 --> 00:05:07,320
to n.

122
00:05:07,320 --> 00:05:11,370
So the space complexity of this solution is of the order of n.