Greedy

You have probably heard the phrase “go with your gut” - greedy algorithms work exactly like that. At every step, they just pick the best-looking option available right now, without worrying about the future.

Sounds too simple to work? For a surprising number of problems, it works perfectly. Let’s dig in.

What is a Greedy Algorithm?

A greedy algorithm solves a problem by making the locally optimal choice at each step - meaning it always picks what looks best at that moment.

It never goes back to reconsider past choices. No replanning, no second-guessing. Just “what’s the best move right now?” - and move on.

Here’s a real-life analogy: imagine you’re at a buffet and you want to fill your plate with the most delicious food possible. A greedy approach says - just pick the tastiest dish you can see right now, then pick the next tastiest, and so on. You don’t plan ahead or save room for dessert strategically. You just keep grabbing the best available option.

Where greedy algorithms shine:

The problem can be broken into steps or choices
Making the best local choice at each step leads to the best overall answer
You don’t need to undo or revisit past choices

The Fractional Knapsack Problem

Imagine you’re a thief with a bag that can carry a maximum weight. There are items with different weights and values. Your goal: maximize the total value you can carry.

The fractional part means you can take a fraction of an item - like scooping half a bag of gold dust.

Example:

Item	Weight	Value	Value per kg
A	10 kg	$60	$6/kg
B	20 kg	$100	$5/kg
C	30 kg	$120	$4/kg

Bag capacity: 50 kg

Greedy strategy: sort items by value per kg (highest first), then fill the bag greedily.

Take all of A (10 kg, $60) - bag has 40 kg left
Take all of B (20 kg, $100) - bag has 20 kg left
Take 2/3 of C (20 kg, $80) - bag is full

Total value = $60 +$ 100 + $80 =$ 240 (maximum possible!)

Implementing Fractional Knapsack

def fractional_knapsack(capacity, items):
    # items is a list of (weight, value) tuples

    # Step 1: Calculate value per unit weight for each item
    # Sort by value/weight ratio in descending order (best first)
    items_with_ratio = []
    for weight, value in items:
        ratio = value / weight
        items_with_ratio.append((ratio, weight, value))

    items_with_ratio.sort(reverse=True)  # highest ratio first

    total_value = 0
    remaining_capacity = capacity

    for ratio, weight, value in items_with_ratio:
        if remaining_capacity == 0:
            break  # bag is full

        # Take as much of this item as possible
        take = min(weight, remaining_capacity)
        total_value += take * ratio  # value proportional to amount taken
        remaining_capacity -= take

    return total_value


# Example usage
items = [(10, 60), (20, 100), (30, 120)]  # (weight, value)
capacity = 50
result = fractional_knapsack(capacity, items)
print(f"Maximum value: ${result}")  # Output: Maximum value: $240.0

Step by step breakdown:

Calculate the value-per-kg ratio for every item
Sort items by this ratio (best bang for weight first)
Keep filling the bag - take the whole item if it fits, otherwise take a fraction
Stop when the bag is full

Time complexity: O(n log n) - dominated by the sorting step.

What is a Spanning Tree?

Before jumping into minimum spanning trees, let’s understand what a spanning tree is.

Given a connected graph (a set of nodes all connected to each other), a spanning tree is a subgraph that:

Connects all the nodes
Has no cycles (no loops)
Uses exactly n - 1 edges (where n is the number of nodes)

Think of it like this: you have 5 cities, and you want to build roads so that every city is reachable from every other city - but you want to use as few roads as possible. That minimal road network is a spanning tree.

Original Graph:        One Spanning Tree:
A - B - C              A - B - C
|   |   |              |
D - E               D   E

A graph can have many different spanning trees. The question is - which one is best?

Minimum Spanning Tree

A Minimum Spanning Tree (MST) is the spanning tree with the smallest total edge weight.

If the edges represent road-building costs, an MST gives you the cheapest way to connect all cities.

Properties of an MST:

Connects all n nodes
Has exactly n - 1 edges
Has the minimum possible total weight among all spanning trees
A graph can have multiple MSTs if some edges have equal weights

There are two classic greedy algorithms to find the MST: Kruskal’s and Prim’s.

Finding MST with Kruskal’s Algorithm

Kruskal’s algorithm builds the MST by greedily adding the cheapest edge that doesn’t create a cycle.

The idea: look at all edges, sorted by weight. Keep adding the cheapest one - but skip any edge that would create a loop.

Sort all edges by weight (cheapest first)
Start with no edges selected (each node is its own isolated component)
Go through edges one by one:
- If adding this edge connects two different components -> add it
- If it would create a cycle (both endpoints already connected) -> skip it
Stop when you have n - 1 edges (all nodes are connected)

# We need a "Union-Find" (Disjoint Set) structure to track components
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # each node is its own parent initially
        self.rank = [0] * n

    def find(self, x):
        # Find the root of x's component (with path compression)
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Merge the components of x and y
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False  # already in same component - would create cycle!
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True  # successfully merged


def kruskal(n, edges):
    # edges is a list of (weight, node1, node2)
    edges.sort()  # sort by weight (cheapest first)

    uf = UnionFind(n)
    mst_edges = []
    total_weight = 0

    for weight, u, v in edges:
        if uf.union(u, v):  # if this doesn't create a cycle
            mst_edges.append((u, v, weight))
            total_weight += weight

        if len(mst_edges) == n - 1:
            break  # MST complete

    return mst_edges, total_weight


# Example: 4 nodes (0,1,2,3), edges as (weight, u, v)
edges = [
    (1, 0, 1),
    (4, 0, 2),
    (3, 1, 2),
    (2, 1, 3),
    (5, 2, 3),
]
mst, cost = kruskal(4, edges)
print("MST edges:", mst)
print("Total cost:", cost)

Time complexity: O(E log E) where E is the number of edges (sorting dominates).

Finding MST with Prim’s Algorithm

Prim’s algorithm grows the MST one node at a time - like growing a tree from a seed.

The idea: start from any node. At each step, add the cheapest edge that connects a node already in your tree to a node not yet in it.

Start with any node (say node 0) in your MST
Look at all edges going from nodes IN your tree to nodes NOT yet in it
Pick the cheapest such edge and add that node to the tree
Repeat until all nodes are in the tree

import heapq  # min-heap for efficiency

def prim(n, adj):
    # adj is an adjacency list: adj[u] = list of (weight, v)
    visited = [False] * n
    min_heap = [(0, 0)]  # (weight, node) - start from node 0 with cost 0
    total_weight = 0
    mst_edges = []

    while min_heap:
        weight, u = heapq.heappop(min_heap)  # get cheapest available edge

        if visited[u]:
            continue  # already added to MST, skip

        visited[u] = True
        total_weight += weight

        if weight != 0:  # skip the starting node (it has no incoming edge)
            mst_edges.append((u, weight))

        # Add all neighbors of u to the heap
        for edge_weight, v in adj[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (edge_weight, v))

    return mst_edges, total_weight


# Example: same graph as before
adj = {
    0: [(1, 1), (4, 2)],
    1: [(1, 0), (3, 2), (2, 3)],
    2: [(4, 0), (3, 1), (5, 3)],
    3: [(2, 1), (5, 2)],
}
mst, cost = prim(4, adj)
print("MST cost:", cost)

Kruskal vs Prim - when to use which:

	Kruskal’s	Prim’s
Best for	Sparse graphs (few edges)	Dense graphs (many edges)
Approach	Sorts all edges globally	Grows from one node
Data structure	Union-Find	Priority queue (min-heap)
Time complexity	O(E log E)	O(E log V) with heap

Dijkstra’s Algorithm - Shortest Path

Dijkstra’s algorithm finds the shortest path from one source node to all other nodes in a graph with non-negative edge weights.

Think of it like this: you’re in a city and want to find the shortest route from your home to every other location. Dijkstra’s algorithm solves this.

The greedy idea: always extend the path to the closest unvisited node next. Once you’ve finalized the shortest distance to a node, you never revisit it.

Set distance to source = 0, distance to all others = infinity
Use a priority queue (min-heap) - always process the node with the smallest known distance next
For each node you process, check all its neighbors:
- If going through this node gives a shorter path to the neighbor -> update the neighbor’s distance
Repeat until all nodes are processed

Start: Node A, all distances = infinity except A = 0

Graph:
A --1-- B
|       |
4       2
|       |
C --1-- D

Step 1: Process A (dist=0) -> update B=1, C=4
Step 2: Process B (dist=1) -> update D=1+2=3
Step 3: Process D (dist=3) -> update C=3+1=4 (no improvement)
Step 4: Process C (dist=4) -> no improvements

Final distances: A=0, B=1, C=4, D=3

Implementing Dijkstra’s Algorithm

import heapq

def dijkstra(n, adj, source):
    # adj[u] = list of (weight, v)
    dist = [float('inf')] * n  # start with infinity for all nodes
    dist[source] = 0
    previous = [-1] * n  # to reconstruct the path later

    min_heap = [(0, source)]  # (distance, node)

    while min_heap:
        current_dist, u = heapq.heappop(min_heap)

        # If we already found a better path, skip this outdated entry
        if current_dist > dist[u]:
            continue

        for weight, v in adj[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:  # found a shorter path!
                dist[v] = new_dist
                previous[v] = u
                heapq.heappush(min_heap, (new_dist, v))

    return dist, previous


def get_path(previous, source, target):
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = previous[current]
    path.reverse()
    return path if path[0] == source else []  # return empty if no path exists


# Example usage
adj = {
    0: [(1, 1), (4, 2)],  # node 0 connects to node 1 (weight 1) and node 2 (weight 4)
    1: [(1, 0), (2, 3)],
    2: [(4, 0), (1, 3)],
    3: [(2, 1), (1, 2)],
}
distances, prev = dijkstra(4, adj, source=0)
print("Shortest distances from node 0:", distances)
print("Path from 0 to 3:", get_path(prev, 0, 3))

Time complexity: O((V + E) log V) using a min-heap, where V is vertices and E is edges.

Huffman Coding - Greedy Compression

Huffman coding is a clever way to compress data by using shorter codes for more frequent characters.

Imagine you’re sending the text “AABBBCCCC”. Instead of using the same number of bits for every character, what if you used fewer bits for the most common ones?

The idea: build a binary tree where more frequent characters are closer to the root (shorter code), and rarer ones are deeper (longer code).

Example: for the string “AABBBCCCC”

Character	Frequency	Without Huffman	With Huffman
A	2	00 (2 bits)	110 (3 bits)
B	3	01 (2 bits)	10 (2 bits)
C	4	10 (2 bits)	0 (1 bit)

With normal encoding: 9 characters x 2 bits = 18 bits With Huffman: 2x3 + 3x2 + 4x1 = 6 + 6 + 4 = 16 bits (saved 2 bits!)

How the greedy algorithm builds the tree:

Count the frequency of each character
Put all characters in a min-heap (lowest frequency = highest priority)
Repeatedly take the two lowest-frequency nodes, merge them into one node (their combined frequency), and put it back
Repeat until only one node remains - that’s your Huffman tree
Assign 0 to left branches and 1 to right branches to get each character’s code

import heapq

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq  # for heap ordering


def build_huffman_tree(text):
    # Step 1: Count frequencies
    freq = {}
    for char in text:
        freq[char] = freq.get(char, 0) + 1

    # Step 2: Build min-heap
    heap = [HuffmanNode(char, f) for char, f in freq.items()]
    heapq.heapify(heap)

    # Step 3: Merge until one node remains
    while len(heap) > 1:
        left = heapq.heappop(heap)   # lowest frequency
        right = heapq.heappop(heap)  # second lowest

        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right

        heapq.heappush(heap, merged)

    return heap[0]  # root of the Huffman tree


def get_codes(node, prefix="", codes={}):
    if node is None:
        return
    if node.char is not None:  # leaf node - actual character
        codes[node.char] = prefix
        return
    get_codes(node.left, prefix + "0", codes)
    get_codes(node.right, prefix + "1", codes)
    return codes


# Example
text = "AABBBCCCC"
root = build_huffman_tree(text)
codes = get_codes(root)
print("Huffman codes:", codes)

# Encode the text
encoded = "".join(codes[char] for char in text)
print(f"Encoded: {encoded}")
print(f"Original bits: {len(text) * 8}, Compressed bits: {len(encoded)}")

Time complexity: O(n log n) where n is the number of unique characters.

Optimal Merge Pattern

Imagine you have several sorted files and you want to merge them all into one sorted file. Each merge of two files costs the sum of their sizes. What order should you merge to minimize total cost?

Greedy strategy: always merge the two smallest files first.

Why it works: smaller merges early on cost less, and those merged results get merged again later. Merging small things first keeps intermediate costs low.

Example: files of sizes [2, 3, 4, 5]

Greedy approach:

Merge 2 and 3 -> cost 5, now have [4, 5, 5]
Merge 4 and 5 -> cost 9, now have [5, 9]
Merge 5 and 9 -> cost 14

Total cost = 5 + 9 + 14 = 28

Compare with a bad order (merge left to right):

Merge 2 and 3 -> cost 5, now [5, 4, 5]
Merge 5 and 4 -> cost 9, now [9, 5]
Merge 9 and 5 -> cost 14

Same total here, but consider sizes [1, 2, 3, 4, 100]:

Greedy: merge small ones first, keep 100 out till last possible moment
Naive: merging 100 early multiplies its cost across many operations

import heapq

def optimal_merge_cost(files):
    heapq.heapify(files)  # convert to min-heap
    total_cost = 0

    while len(files) > 1:
        first = heapq.heappop(files)   # smallest
        second = heapq.heappop(files)  # second smallest
        merged = first + second
        total_cost += merged
        heapq.heappush(files, merged)  # put merged file back

    return total_cost


files = [2, 3, 4, 5]
print("Minimum merge cost:", optimal_merge_cost(files))  # Output: 28

This is essentially the same logic as Huffman coding - both use a min-heap to greedily merge the two smallest elements.

Job Scheduling with Deadlines

You have a bunch of jobs, each with a deadline and a profit. Each job takes exactly 1 unit of time. You can do only one job at a time. Maximize your total profit by choosing which jobs to do and when.

Example:

Job	Deadline	Profit
J1	2	$100
J2	1	$19
J3	2	$27
J4	1	$25
J5	3	$15

Greedy strategy: sort jobs by profit (highest first). For each job, schedule it as late as possible before its deadline (this keeps earlier slots free for other jobs).

J1 ($100, deadline 2) -> schedule at slot 2
J2 ($19, deadline 1) -> schedule at slot 1… but slot 1 is available, take it
J4 ($25, deadline 1) -> slot 1 is taken, deadline is 1, skip
J3 ($27, deadline 2) -> slot 2 is taken, try slot 1… taken too, skip
J5 ($15, deadline 3) -> schedule at slot 3

Chosen jobs: J1, J2, J5. Profit = $100 +$ 19 + $15 = **$ 134**

def job_scheduling(jobs):
    # jobs is a list of (job_id, deadline, profit)
    # Sort by profit descending (greedy - best profit first)
    jobs.sort(key=lambda x: x[2], reverse=True)

    max_deadline = max(job[1] for job in jobs)
    slots = [None] * (max_deadline + 1)  # slots[0] unused, slots[1..max_deadline]
    total_profit = 0
    chosen_jobs = []

    for job_id, deadline, profit in jobs:
        # Find the latest available slot at or before the deadline
        for slot in range(deadline, 0, -1):
            if slots[slot] is None:  # slot is free
                slots[slot] = job_id
                total_profit += profit
                chosen_jobs.append(job_id)
                break  # job scheduled, move to next job

    return chosen_jobs, total_profit


jobs = [
    ("J1", 2, 100),
    ("J2", 1, 19),
    ("J3", 2, 27),
    ("J4", 1, 25),
    ("J5", 3, 15),
]
chosen, profit = job_scheduling(jobs)
print("Chosen jobs:", chosen)
print("Total profit:", profit)

Time complexity: O(n^2) for the basic version. Can be improved to O(n log n) using Union-Find.

When Greedy Works (and When It Doesn’t)

Greedy algorithms are elegant and fast, but they’re not always correct. Here’s how to tell:

Greedy works when:

The problem has optimal substructure - the best overall solution contains the best solutions to its sub-problems
It has the greedy choice property - making the locally best choice at each step leads to the globally best solution

Greedy fails when:

Future choices are affected by current choices in complex ways
Taking the best option now closes off better options later

Classic example where greedy fails - 0/1 Knapsack:

Items: weight 1 (value $1), weight 5 (value$ 6), weight 6 (value $10). Capacity: 6.

Greedy (by ratio): takes weight-5 item first ( $6/5 =$ 1.2/unit), then can’t fit anything else. Total: $6
Optimal: take weight-1 + weight-5 -> wait, that’s 6 total. Actually: $1 +$ 6 = $7. Or just the weight-6 item for$ 10.
Greedy might pick wrong here depending on the specific numbers.

The fix for 0/1 knapsack? Dynamic programming - which exhaustively tries all combinations.

Quick Reference

Fractional Knapsack

Sort items by value-per-weight ratio. Take as much of the best item as possible, then move to the next. Works because you can take fractions.

Kruskal's MST

Sort all edges by weight. Add the cheapest edge that doesn’t create a cycle. Uses Union-Find to detect cycles efficiently.

Prim's MST

Start from one node. Always add the cheapest edge connecting your current tree to a new node. Uses a min-heap for efficiency.

Dijkstra's Shortest Path

Always process the closest unvisited node next. Update neighbors if a shorter path is found. Only works with non-negative weights.

Huffman Coding

Merge the two lowest-frequency nodes repeatedly. Results in shorter codes for frequent characters. Used in file compression.

Job Scheduling

Sort jobs by profit. Schedule each job at the latest available slot before its deadline. Maximizes total profit.

Summary

Greedy algorithms make the locally best choice at each step without looking back
They work when the problem has optimal substructure and the greedy choice property
They’re usually fast (O(n log n)) and simple to implement
They DON’T always give the optimal answer - know when to use dynamic programming instead