Greedy Fundamentals

1. Introduction

What is a Greedy Algorithm?

A Greedy Algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It makes locally optimal choices at each stage with the hope of finding a global optimum.

Why study them?

Greedy algorithms are highly optimal, often running in O(N) or O(N log N) time with O(1) space. However, they do not work for all optimization problems. Understanding how to prove greedy correctness and identify when a problem requires Dynamic Programming (DP) is a core interview capability.

Where is it Used?

Data Compression: Huffman coding uses a greedy tree build to compress text databases.

Minimum Spanning Trees: Kruskal's and Prim's algorithms choose the cheapest edges greedily.

---

2. Mental Model: The Greedy Shopper

Imagine you are in a supermarket and are allowed to grab 5 items for free:

A Greedy Shopper immediately runs to the electronics aisle and grabs the 5 most expensive TVs on the shelves now. They make their choice instantly without analyzing shelf layout combinations.

A Dynamic Programming Shopper sits down, calculates the total price of all possible combinations of items on all shelves, and finds the absolute highest value combination.

The greedy choice is fast and works perfectly here because grabbing the most valuable TV now never prevents you from grabbing other valuable items later.

---

3. Core Properties & Trade-offs

To apply a greedy approach, a problem must satisfy two properties: 1. Greedy Choice Property: A global optimal solution can be arrived at by making locally optimal (greedy) choices. 2. Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.

Greedy vs Dynamic Programming vs Backtracking

Let's look at the Coin Change problem (making change for target T with fewest coins):

denominations = [1, 2, 5, 10] (standard): Greedy works. To make change for 16, we greedily take 10, then 5, then 1 (3 coins).

denominations = [1, 3, 4] (arbitrary): Greedy fails. To make change for 6, greedy picks 4 followed by two 1s (4 + 1 + 1 = 3 coins). However, the global optimum is two 3s (3 + 3 = 2 coins). This requires Dynamic Programming.

---

4. Visual Decision Choice Comparison

Comparing decision path choices for target 6 with coins [1, 3, 4]:

---

5. Real-World Examples

Cash Register Dispersal: Cashiers counting dollar bills and coins back to customers using the largest denominations first.

Min-Cost Electrical Grids: Implementing Kruskal's algorithm to wire computer terminals with the minimum overall length of copper cabling.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test structural assumptions:

"Given task intervals, find the maximum schedule overlaps." -> Interval scheduling. Proving that sorting by end-times yields optimal schedules is key.

"When is greedy not the optimal solution?" -> Explain that if local choices restrict future possibilities, greedy fails. Demonstrate using the arbitrary coin set [1, 3, 4] or Knapsack constraints.

Common Mistakes

> 2. Forgetting to Sort: Greedy algorithms frequently require sorted input data (e.g. sorting by weights, values, start times, or end times). Skipping sorting violates greedy assumptions.

---

7. Summary

Greedy choice: Locally optimal choices, never backtracking.

Requirements: Greedy Choice Property + Optimal Substructure.

DP contrast: Use DP if local choices block overall path combinations.

---

8. Quiz

Question 1: Why is Dijkstra's algorithm classified as a Greedy algorithm?

Answer: Dijkstra's is greedy because at each step it extracts the vertex with the absolute minimum distance from the priority queue and finalizes its path cost, assuming no future paths can reduce its cost.

Question 2: Does the greedy choice property guarantee that a greedy algorithm will find the optimal solution?

Answer: Yes. If a problem mathematically satisfies the greedy choice property and optimal substructure, a greedy algorithm is guaranteed to yield the global optimum.

Question 3: If target is 11 and coin denominations are [1, 5, 6, 8], does greedy make optimal change?

Answer: No. Greedy picks 8 + 1 + 1 + 1 (4 coins), whereas the optimal selection is 6 + 5 (2 coins).

Question 4: True or False: Greedy algorithms generally use more memory than Dynamic Programming.

Answer: False. Greedy algorithms only track the current state, running in O(1) auxiliary space. DP stores solutions to all subproblems in matrices/arrays, requiring O(N) or O(N²) space.

Question 5: What is the benefit of sorting elements by value-to-weight ratio in the Fractional Knapsack problem?

Answer: It maximizes the value density packed per unit of weight. Because items can be split fractionally, taking the densest item first guarantees the optimal total value.