1
00:00:00,170 --> 00:00:02,030
Hey there and welcome back!

2
00:00:02,030 --> 00:00:08,720
In this video we are getting started with another algorithmic approach which is the greedy algorithm.

3
00:00:08,720 --> 00:00:15,320
Now, before we get started and deal with real coding interview questions, these are the four things

4
00:00:15,320 --> 00:00:16,970
that we will first discuss.

5
00:00:16,970 --> 00:00:17,330
Okay.

6
00:00:17,330 --> 00:00:21,110
So first we will try to understand what the greedy algorithm is.

7
00:00:21,110 --> 00:00:24,740
Then we'll try to understand what it is used for.

8
00:00:24,740 --> 00:00:30,110
And after that we'll discuss what problems are suited for greedy algorithms.

9
00:00:30,110 --> 00:00:35,480
And finally we will compare the greedy approach with dynamic programming.

10
00:00:35,480 --> 00:00:36,140
All right.

11
00:00:36,140 --> 00:00:37,640
So let's get started.

12
00:00:37,640 --> 00:00:41,690
First let's discuss what the greedy algorithm is.

13
00:00:41,690 --> 00:00:49,730
Actually, now we know that an algorithm is a series of steps or instructions used to solve a problem.

14
00:00:49,730 --> 00:00:50,180
Okay.

15
00:00:50,180 --> 00:00:57,110
Now when it comes to the greedy algorithm, this is a type of algorithm or a way of solving problems,

16
00:00:57,110 --> 00:01:05,420
which is build step by step where the solution is built step by step, and at each step the algorithm

17
00:01:05,420 --> 00:01:09,950
makes the choice that gives the highest immediate benefit.

18
00:01:09,950 --> 00:01:13,100
Okay, so the key word over here is immediate.

19
00:01:13,100 --> 00:01:17,030
The algorithm obviously would have to make choices at each step.

20
00:01:17,030 --> 00:01:24,170
And the way that it decides which choice to make is by checking which choice gives the highest immediate

21
00:01:24,170 --> 00:01:24,800
benefit.

22
00:01:24,800 --> 00:01:27,530
Now let's try to understand this a little bit better.

23
00:01:27,530 --> 00:01:29,660
And for this let's take an example.

24
00:01:29,660 --> 00:01:37,130
Let's say there are two cities A and B, and a person wants to travel from A to B, and there are these

25
00:01:37,130 --> 00:01:37,970
three paths.

26
00:01:37,970 --> 00:01:41,450
And for traveling this path you'll have to spend $5.

27
00:01:41,450 --> 00:01:45,620
And then for traveling this part over here, you'll have to pay $100.

28
00:01:45,620 --> 00:01:49,940
And in a similar manner these paths also have their respective costs.

29
00:01:49,940 --> 00:01:53,090
For example, this path over here costs $10.

30
00:01:53,090 --> 00:01:56,630
And for example, this path over here costs $2.

31
00:01:56,630 --> 00:02:05,660
And the person wants to go from point A to point B in a way that minimizes the cost for traveling from

32
00:02:05,660 --> 00:02:06,410
A to B.

33
00:02:06,440 --> 00:02:13,250
Now, if we were to approach this with a greedy algorithm, like if you were to try to find the solution

34
00:02:13,250 --> 00:02:20,660
for this using a greedy algorithm, we would make the choice at every step that gives us the highest

35
00:02:20,660 --> 00:02:21,740
immediate benefit.

36
00:02:21,740 --> 00:02:27,170
So the person initially is at point A, and the person has to choose which way to go, whether to go

37
00:02:27,170 --> 00:02:29,600
this way, this way, or this way.

38
00:02:29,600 --> 00:02:36,410
Now when you compare these three costs, you can see that the minimum cost is this over here, because

39
00:02:36,410 --> 00:02:37,490
this is just five.

40
00:02:37,490 --> 00:02:42,170
And therefore this choice gives the highest immediate benefit.

41
00:02:42,170 --> 00:02:45,830
And therefore the greedy algorithm would go ahead and choose this path.

42
00:02:45,830 --> 00:02:52,310
But then after you reach over here, you can see that to reach point B from here you have to pay $100,

43
00:02:52,310 --> 00:02:55,010
which is significantly higher than these paths.

44
00:02:55,040 --> 00:02:55,370
Okay.

45
00:02:55,370 --> 00:03:02,300
So this means that probably this question over here is not a good problem for the greedy approach.

46
00:03:02,300 --> 00:03:07,850
But again, we're just trying to understand what it means with making the choice at every step such

47
00:03:07,850 --> 00:03:10,460
that it gives the highest immediate benefit.

48
00:03:10,460 --> 00:03:12,350
Okay, so that's what this would do over here.

49
00:03:12,350 --> 00:03:15,530
The greedy algorithm would just go ahead and choose this path.

50
00:03:15,530 --> 00:03:18,890
And we see that it's not the optimal path for solving this question.

51
00:03:18,890 --> 00:03:26,210
Now another important thing to note about the greedy algorithm is that it does not reconsider its choices.

52
00:03:26,210 --> 00:03:28,040
Now what does this mean?

53
00:03:28,040 --> 00:03:34,160
It means that once the algorithm makes this choice and reaches over here, it would never get back and

54
00:03:34,160 --> 00:03:39,980
reconsider this choice and consider what the cost would be if it had made this choice, for example.

55
00:03:39,980 --> 00:03:43,310
Okay, so it does not reconsider its choices.

56
00:03:43,310 --> 00:03:49,970
And in one of the future videos, we'll see that this is one of the major differences between the greedy

57
00:03:49,970 --> 00:03:52,400
algorithm and dynamic programming.

58
00:03:52,400 --> 00:03:58,610
Now, to further solidify what we have discussed over here, let's take one more example.

59
00:03:58,610 --> 00:04:06,590
Let's consider this problem where we have a sack over here or a bag, and this bag has a capacity of

60
00:04:06,590 --> 00:04:07,610
two kilograms.

61
00:04:07,610 --> 00:04:13,370
And we have these four bags over here, which each weighs one kilogram.

62
00:04:13,370 --> 00:04:15,470
And this one is made up of gold.

63
00:04:15,470 --> 00:04:17,270
This is made up of bronze.

64
00:04:17,270 --> 00:04:21,680
This is one kilogram of diamonds and this is one kilogram of iron okay.

65
00:04:21,680 --> 00:04:29,030
And let's say we are trying to maximize the value that can be added into the bag such that this constraint

66
00:04:29,030 --> 00:04:29,600
is met.

67
00:04:29,600 --> 00:04:34,220
That is, the maximum capacity that can be added to the bag is two kilogram.

68
00:04:34,220 --> 00:04:41,930
Now, if we were to approach this with a greedy algorithm, we would make choices at every step such

69
00:04:41,930 --> 00:04:44,870
that it gives the highest immediate benefit.

70
00:04:44,870 --> 00:04:50,930
So when you take a look at this, because over here you have gold, diamond, iron and bronze and all

71
00:04:50,930 --> 00:04:52,730
of these are just one kilogram.

72
00:04:52,730 --> 00:04:59,630
So the best choice that would give me the highest immediate benefit would be to add one.

73
00:04:59,800 --> 00:05:02,350
Kilogram of diamonds to this bag over here.

74
00:05:02,380 --> 00:05:08,110
Okay, because one kilogram of diamonds has the highest value among these four items.

75
00:05:08,110 --> 00:05:11,650
So this is the first choice that the greedy algorithm makes.

76
00:05:11,650 --> 00:05:16,330
And at this point, we have added only items worth one kilogram to the bag.

77
00:05:16,330 --> 00:05:21,520
And we can still add one more kilogram to the bag because the capacity is two kilograms.

78
00:05:21,520 --> 00:05:24,250
And therefore I would again make the choice.

79
00:05:24,250 --> 00:05:30,430
That is, I would choose among these three the item that would give me the highest immediate benefit,

80
00:05:30,430 --> 00:05:35,260
and that would be by adding one kilogram of gold to this bag over here.

81
00:05:35,260 --> 00:05:38,290
And by now we have exhausted the capacity.

82
00:05:38,290 --> 00:05:45,010
And this is how we would fill the bag such that this constraint is met and the value in the bag is maximized.

83
00:05:45,010 --> 00:05:51,550
You can notice that this problem over here is a good problem for the greedy algorithm or greedy approach.

84
00:05:51,550 --> 00:05:57,880
Again, notice that this question is similar, but a little bit different from the zero one knapsack

85
00:05:57,880 --> 00:06:00,280
problem, which we have previously discussed.

86
00:06:00,280 --> 00:06:05,560
Okay, in the zero one knapsack problem, the difference was that we had different items, but their

87
00:06:05,560 --> 00:06:06,610
weights were different.

88
00:06:06,610 --> 00:06:07,000
Okay.

89
00:06:07,000 --> 00:06:11,410
And that's why the zero one knapsack problem cannot be solved using a greedy approach.

90
00:06:11,410 --> 00:06:15,340
And rather it requires dynamic programming for solving this question.

91
00:06:15,340 --> 00:06:20,680
We have already discussed this in a previous video, but I have slightly modified this question, and

92
00:06:20,680 --> 00:06:24,280
I've made every item over here to have the same weight.

93
00:06:24,280 --> 00:06:29,770
So you have one kilogram over here, one kilogram over here, and one kilogram for these two as well.

94
00:06:29,770 --> 00:06:31,030
And we have seen that.

95
00:06:31,030 --> 00:06:31,450
How?

96
00:06:31,450 --> 00:06:33,100
By making this tweak.

97
00:06:33,100 --> 00:06:36,460
This problem became a good problem for the greedy approach.

98
00:06:36,460 --> 00:06:43,420
Or we were able to maximize the value in the bag by just picking items that had the highest immediate

99
00:06:43,420 --> 00:06:44,980
benefit at every step.

100
00:06:44,980 --> 00:06:47,860
And that is what the greedy algorithm does.

101
00:06:47,860 --> 00:06:53,050
So by this point, we have got a good understanding of what the greedy algorithm is.

102
00:06:53,050 --> 00:06:59,710
Basically, it's an algorithm that builds the solution step by step, and at every step the algorithm

103
00:06:59,710 --> 00:07:03,700
makes the choice that gives the highest immediate benefit.

104
00:07:03,700 --> 00:07:11,590
Now, in other words, we can say that the greedy algorithm chooses the locally optimal choice at every

105
00:07:11,590 --> 00:07:15,580
step, hoping to find the global optimum.

106
00:07:15,580 --> 00:07:22,300
Now, with local optimum, all that we mean is the choice at that particular instance which gives the

107
00:07:22,300 --> 00:07:24,130
highest immediate benefit.

108
00:07:24,130 --> 00:07:31,840
And with global optimum, we mean that the final solution has the optimal answer, or we arrive at the

109
00:07:31,840 --> 00:07:39,070
optimal solution to the problem by making these series of choices where at every choice, we were not

110
00:07:39,070 --> 00:07:45,520
thinking about the whole problem or the global best solution, but at every choice we were just focusing

111
00:07:45,520 --> 00:07:51,520
on the locally optimal choice or the choice that would provide the highest immediate benefit.

112
00:07:51,520 --> 00:07:55,150
So this is what the greedy algorithm is all about.

113
00:07:55,150 --> 00:07:59,980
So we have got a good understanding of what the greedy algorithm is.

114
00:07:59,980 --> 00:08:05,440
In the next video let's discuss what the greedy algorithms are used for.