Greedy Algorithms

Sumit Mishra — Wed, 15 Apr 2026 21:52:41 +0000

A greedy algorithm is a problem-solving strategy that builds up a solution piece by piece always choosing the option that looks best right now, without worrying about the future consequences of that choice.

The word "greedy" is apt: the algorithm grabs the most attractive option at each step, pockets it, and moves on. There's no backtracking, no second-guessing, no looking ahead. Just one decisive move after another.

In one line: Make the locally optimal choice at each step and hope it leads to a globally optimal solution.

Think of it like eating the biggest slice of pizza first at a party. You're not thinking about whether someone else might want it, you're just making the best move for you, right now.Greedy algorithms don't reconsider past decisions. Once a choice is made, it's final. This makes them fast and easy to implement, but not always correct for every problem — that's the tradeoff.

Why Use Greedy?

Fast Usually O(n log n) or better, much faster than dynamic programming.
Simple Easy to code and understand. No complex state tracking needed.
Optimal (sometimes) For certain problems, greedy always gives the correct answer.

Greedy works best when the problem has two properties:

Greedy Choice Property: A global solution can be reached by making locally optimal choices.
Optimal Substructure: An optimal solution contains optimal solutions to its sub-problems.

If these hold, greedy is your best friend. If not, you may need dynamic programming or backtracking instead.

A Simple Example: Coin Change

You need to give change of ₹36 using the fewest coins possible. Available coins: 25, 10, 5, 1.

The greedy approach: always pick the largest coin that fits.

Step         Remaining       Coin Picked
1           36                   25
2           11                   10
3            1                    1

Result: 3 coins. Simple and optimal for standard coin systems.

def coin_change(coins, amount):
    # Sort coins in descending order (largest first)
    coins.sort(reverse=True)
    result = []

    for coin in coins:
        # Use as many of this coin as possible
        while amount >= coin:
            amount -= coin
            result.append(coin)

    return result


# Example
coins = [25, 10, 5, 1]
amount = 36
print(coin_change(coins, amount))
# Output: [25, 10, 1]  → 3 coins

Note: Greedy coin change only works for standard coin systems. For arbitrary denominations (e.g. coins = [1, 3, 4], amount = 6), greedy may fail. Use Dynamic Programming instead.

Popular Greedy Problems

Here are three classic problems where greedy shines — each with a clear explanation and clean Python code.

Activity Selection Problem

You have a list of activities, each with a start time and end time. You can only do one activity at a time. Pick the maximum number of activities you can attend.

Greedy idea: Always pick the activity that ends the earliest. This leaves the most room for future activities.

def fractional_knapsack(capacity, items):
    # items = list of (value, weight)
    # Sort by value-to-weight ratio, highest first
    items.sort(key=lambda x: x[0] / x[1], reverse=True)

    total_value = 0.0

    for value, weight in items:
        if capacity <= 0:
            break

        if weight <= capacity:
            # Take the whole item
            total_value += value
            capacity -= weight
        else:
            # Take a fraction of the item
            total_value += value * (capacity / weight)
            capacity = 0

    return round(total_value, 2)

Huffman Encoding

Given characters and their frequencies, build an optimal prefix code (binary tree) that minimizes total encoding length. Used in real-world compression (ZIP, JPEG).

Greedy idea: Always merge the two least frequent nodes. Characters used less get longer codes; frequent ones get shorter codes

import heapq

def build_huffman(freq):
    heap = [[weight, [char, ""]] for char, weight in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)

        # Assign '0' to left branch, '1' to right
        for pair in lo[1:]: pair[1] = '0' + pair[1]
        for pair in hi[1:]: pair[1] = '1' + pair[1]

        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    return sorted(heap[0][1:], key=lambda x: len(x[1]))


freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}

for char, code in build_huffman(freq):
    print(f"{char}: {code}")

# f: 0   (most frequent → shortest code)
# a: 1100 (least frequent → longest code)

When NOT to Use Greedy

Greedy is not a silver bullet. It fails when local best choices don't lead to a global best. A classic example is the 0/1 Knapsack problem — where you can't split items, so grabbing the highest ratio item first may block a better combination.

Problem              Greedy Works?  Better Approach
Activit Selection      ✅ Yes                —
Fractional Knapsack    ✅ Yes                —
Huffman Encoding       ✅ Yes                —
0/1 Knapsack           ❌ No          Dynamic Programming
Shortest Path (general) ❌ No         Dijkstra / Bellman-Ford
Coin Change (arbitrary) ❌ No         Dynamic Programming

Key Takeaways

Greedy = Fast + Simple, but verify it works for your specific problem before committing to it.

Greedy algorithms are a powerful first tool to reach for. They're fast, easy to implement, and provably optimal for many classic problems. The key is recognising when the greedy choice property holds — and when you need to step up to dynamic programming.

A good rule of thumb: Can I prove that always picking the local best never hurts the global best? If yes — go greedy!

Applied Mathematics

Sumit Mishra — Wed, 15 Apr 2026 21:11:48 +0000

Applied mathematics is the branch of mathematics that deals with the use of mathematical methods and techniques to solve real-world problems in science, engineering, business, medicine, and other fields. Unlike pure mathematics, which focuses on abstract concepts for their own sake, applied mathematics is driven by practical applications. it uses tools like calculus, statistics, linear algebra, differential equations, and numerical analysis to model and analyze physical phenomena, optimize systems, predict outcomes, and make decisions. It serves as a bridge between theoretical mathematical ideas and their practical use in areas such as physics, computer science, economics, biology, and engineering, making it an essential foundation for much of modern technology and scientific advancement.

DEV Community: Sumit Mishra

Greedy Algorithms

Why Use Greedy?

Popular Greedy Problems

When NOT to Use Greedy

Key Takeaways

Applied Mathematics