1
00:00:00,140 --> 00:00:01,130
Welcome back.

2
00:00:01,130 --> 00:00:05,990
In the previous videos we have discussed what the greedy algorithm is.

3
00:00:06,020 --> 00:00:12,290
We have also discussed what greedy algorithms are used for, which is basically for optimization problems.

4
00:00:12,290 --> 00:00:18,290
And we have also seen that even though greedy algorithms are used for optimization problems, a greedy

5
00:00:18,290 --> 00:00:24,890
algorithm does not guarantee to give an optimal solution for every problem, and therefore it would

6
00:00:24,890 --> 00:00:31,820
imply that using a greedy algorithm is suitable only for a certain type of problems.

7
00:00:31,820 --> 00:00:37,520
Now that brings us to the question that we're going to discuss in this video, which is what problems

8
00:00:37,520 --> 00:00:40,430
are suitable for greedy algorithms.

9
00:00:40,430 --> 00:00:46,910
Now, when you analyze problems that are suitable for greedy algorithms, you will see that these problems

10
00:00:46,910 --> 00:00:48,680
have two properties.

11
00:00:48,680 --> 00:00:56,630
The two properties that a problem needs to have are the greedy choice property and optimal substructure.

12
00:00:56,630 --> 00:00:59,360
Now let's try to understand these two properties.

13
00:00:59,360 --> 00:01:05,960
And then let's compare whether the two problems that we had previously discussed satisfy these two properties

14
00:01:05,960 --> 00:01:06,590
or not.

15
00:01:06,590 --> 00:01:07,970
So let's get started.

16
00:01:07,970 --> 00:01:11,240
The first property is the greedy choice property.

17
00:01:11,240 --> 00:01:21,020
This property says that the global optimum can be obtained by choosing local optimum at each step.

18
00:01:21,020 --> 00:01:23,660
Okay, so that's the greedy choice property.

19
00:01:23,660 --> 00:01:30,260
Now if a problem satisfies this then probably we can solve that problem with the greedy algorithm.

20
00:01:30,260 --> 00:01:32,390
Now again more of that later.

21
00:01:32,390 --> 00:01:38,390
And as we go ahead and discuss real coding interview questions, we'll also try to understand how those

22
00:01:38,390 --> 00:01:41,600
problems satisfy the greedy choice property.

23
00:01:41,600 --> 00:01:43,550
But more of that coming up soon.

24
00:01:43,550 --> 00:01:48,830
Now what is the second property that problems suitable for greedy algorithms have?

25
00:01:48,830 --> 00:01:56,150
The second property is optimal substructure, and with optimal substructure we mean that the optimal

26
00:01:56,150 --> 00:02:02,180
solution to a problem contains within it the optimal solution to subproblems.

27
00:02:02,180 --> 00:02:09,860
Or in other words, you can think of it in this manner that a problem can be broken down into smaller

28
00:02:09,860 --> 00:02:17,060
related problems, such that the optimal solution to the overall problem can be constructed from the

29
00:02:17,060 --> 00:02:19,220
optimal solution to its subproblems.

30
00:02:19,220 --> 00:02:23,900
And again, this is something that we have discussed when we discussed dynamic programming as well.

31
00:02:23,900 --> 00:02:31,940
So these are the two properties that indicate that a problem can be solved using a greedy algorithm

32
00:02:31,940 --> 00:02:32,600
okay.

33
00:02:32,600 --> 00:02:33,350
All right.

34
00:02:33,350 --> 00:02:40,220
Now in the next video let's go ahead and come to the final topic in this section, which is to compare

35
00:02:40,220 --> 00:02:43,070
the greedy approach with dynamic programming.