Greedy Algorithm — Explained with Examples

A greedy algorithm makes the locally optimal choice at each step, hoping to find a global optimum without revisiting decisions.

Greedy algorithms build a solution piece by piece, always picking the option that looks best at the moment. They never backtrack or reconsider choices. Classic examples include Dijkstra’s algorithm (shortest path), Huffman coding (optimal prefix codes), and the coin change problem (with canonical coin systems). Greedy works when local optimality leads to global optimality — a property called the greedy choice property.

Think of a greedy algorithm like eating a buffet. You grab the most appealing dish first, then the next most appealing, never regretting or returning food. If the buffet is arranged well (greedy-compatible problem), you end up with a great meal. But sometimes, skipping the appetizer for the main course would have been better — that is where greedy fails.

Not all problems are greedy-compatible. For example, the 0/1 knapsack problem requires DP because a greedy approach (pick highest value-to-weight ratio) can miss the optimal combination.

# Coin change with greedy (works for USD denominations)
def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result if amount == 0 else None

# Dijkstra's algorithm (simplified greedy)
import heapq
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_dist, node = heapq.heappop(pq)
        if current_dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

print(coin_change_greedy([25, 10, 5, 1], 67))
# Output: [25, 25, 10, 5, 1, 1]

Greedy algorithms are fast (often O(n log n) or O(n)) and simple to implement. Always prove or test that the greedy choice property holds for your specific problem.

Dynamic Programming, Divide and Conquer, Algorithm, Sorting Algorithms

DP vs Greedy