Introduction to Greedy
What makes an algorithm greedy? Learn the greedy choice property and when greedy solutions work.
36 lessons
93 min
Codeforces: 800-1200LeetCode: 1200-1500
Lessons
1. Intro
Why greedy matters
2m
2. The Core Idea
Local choices, global optimum
3m
3. Vocabulary - Greedy Choice
The first property
3m
4. Vocabulary - Optimal Substructure
Subproblems stay optimal
3m
5. Quiz: Two Properties
Test your understanding
1m1 problems
6. When Greedy Works
Recognizing the pattern
3m
7. When Greedy Fails
The warning signs
3m
8. Greedy vs Brute Force
Why greedy is faster
3m
9. Greedy vs Dynamic Programming
The key difference
3m
10. Quiz: Greedy vs DP
Know the difference
1m1 problems
11. The Greedy Template
Common structure
3m
12. Example - Coin Change (Greedy Works)
Standard denominations
3m
13. Why Greedy Works for US Coins
The canonical property
3m
14. Example - Coin Change (Greedy Fails)
Non-standard denominations
3m
15. Lesson from Coin Change
Know your input
3m
16. Quiz: Coin Change
Greedy or DP?
1m1 problems
17. Problem - Assign Cookies
Entry-level greedy
3m1 problems
18. Assign Cookies - The Idea
Match smallest to smallest
3m
19. Assign Cookies - Algorithm
Two-pointer approach
3m
20. Assign Cookies - Walkthrough
Tracing the algorithm
3m
21. Assign Cookies - Implementation
The code
3m1 problems
22. Assign Cookies - Why Greedy Works
Proof sketch
3m
23. Lessons from Assign Cookies
summary
2m
24. Problem - Lemonade Change
Making change greedily
3m1 problems
25. Lemonade - The Idea
Prefer giving $10 bills
3m
26. Lemonade - Algorithm
Track your bills
3m
27. Lemonade - Implementation
The code
3m1 problems
28. Quiz: Lemonade Greedy Choice
Why prefer $10?
1m1 problems
29. Lessons from Lemonade
Resource flexibility
2m
30. The Sorting Question
What to sort by?
3m
31. Common Greedy Patterns
Recognizing problem types
3m
32. The Greedy Mindset
How to think
3m
33. Quiz: Greedy Mindset
Apply the thinking
1m1 problems
34. Time Complexity of Greedy
Usually fast
3m
35. What is Next
Looking ahead
2m
36. Section Recap
What we learned
2m
Practice Problems
1.
Bun Lovercodeforces
2.
Deadly Lasercodeforces
3.
Death Sortcodeforces
4.
Wonderful Coloring - 1codeforces
5.
Cyphercodeforces
6.
Expressioncodeforces
7.
Double Stringscodeforces
8.
Gold Rushcodeforces
9.
Comparing Two Long Integerscodeforces
10.
Fencecodeforces
11.
Dora and Searchcodeforces
12.
Challenging Valleyscodeforces