Friday Night Wiki
TopicsAbout
Buy me a coffee
Algorithms Tutorial

Greedy and Divide-and-Conquer: Two Useful Hammers

This chapter covers greedy algorithms, divide-and-conquer, when each works, and how to tell the difference from DP.

Greedy

A greedy algorithm makes the locally optimal choice at each step and hopes it adds up to the globally optimal solution.

Sometimes it works beautifully: Dijkstra, Prim, Kruskal, Huffman coding.

Sometimes it fails: coin change with weird denominations.

The hard part isn't writing greedy code. It's proving your greedy choice is correct. If you can't prove it, you need DP.

When Greedy Works

Two properties:

  • Greedy choice property: a global optimum can be reached by making the locally optimal choice.
  • Optimal substructure: after the greedy choice, what's left is a smaller optimization problem with the same shape.

You won't always know if these hold. In interviews and practice, build intuition by recognizing the pattern: classic greedy problems show up again and again.

Classic Greedy Problems

Interval Scheduling

Given a set of activities with start and end times, select the maximum number of non-overlapping activities.

Greedy rule: always pick the activity that ends earliest.

def max_activities(intervals):
    intervals.sort(key=lambda x: x[1])    # sort by end time
    count = 0
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

O(n log n) for sorting. Provably optimal: picking the earliest-ending activity leaves the most room for the rest.

Fractional Knapsack

Same as 0/1 knapsack, but you can take fractions of items.

Greedy rule: take items in order of value-per-weight until full.

def fractional_knapsack(weights, values, capacity):
    items = sorted(zip(weights, values), key=lambda x: -x[1] / x[0])
    total = 0.0
    for w, v in items:
        if capacity >= w:
            total += v
            capacity -= w
        else:
            total += v * (capacity / w)
            break
    return total

O(n log n). 0/1 knapsack needs DP; fractional knapsack is greedy.

Coin Change (Canonical Denominations)

With US coins (1, 5, 10, 25), greedy works: always take the largest coin that fits.

def coin_change_greedy(amount, coins=[25, 10, 5, 1]):
    count = 0
    for c in coins:
        count += amount // c
        amount %= c
    return count

But with denominations like [1, 3, 4] and amount 6: greedy gives 4 + 1 + 1 = 3 coins. Optimal is 3 + 3 = 2 coins.

For arbitrary denominations, greedy fails. You need DP (Chapter 9).

Huffman Coding

Given character frequencies, build a prefix code that minimizes total encoded length.

Greedy rule: repeatedly merge the two least-frequent nodes.

import heapq
from collections import Counter

def huffman(text):
    freq = Counter(text)
    heap = [[f, [c, ""]] for c, f in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        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 {char: code for char, code in heap[0][1:]}

Always combining the two least-frequent symbols gives the optimal prefix code. Used in file compression (ZIP, gzip).

When Greedy Fails

The tell: you find a counterexample where the greedy choice leads to a worse outcome. If you can't prove greedy works and you can't find a counterexample, try small cases by hand.

Common failure modes:

  • Coin change with weird denominations.
  • 0/1 knapsack (greedy by value/weight ratio fails).
  • Traveling salesman (nearest neighbor heuristic isn't optimal).

When greedy fails, fall back to DP or brute-force search.

Divide-and-Conquer

Break a problem into subproblems, solve each, combine the results.

Three steps:

  1. Divide the problem into subproblems.
  2. Conquer each subproblem (usually recursively).
  3. Combine results into an answer for the original problem.

Merge Sort (Again)

Classic D&C.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # divide
    right = merge_sort(arr[mid:])    # divide
    return merge(left, right)        # combine

T(n) = 2T(n/2) + O(n). By the Master Theorem, T(n) = O(n log n).

Fast Exponentiation

Compute x^n in O(log n) instead of O(n).

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)
    if n % 2 == 0:
        return half * half
    else:
        return half * half * x

Each call halves n. O(log n) time, O(log n) space for recursion.

Binary Search (Again)

Also divide-and-conquer. Halve the range, recurse (or iterate) on the relevant half.

Karatsuba Multiplication

Multiplying two n-digit numbers with schoolbook is O(n^2). Karatsuba divides each number into halves and reduces 4 multiplications to 3, giving O(n^1.58).

You'll rarely implement Karatsuba. You'll sometimes meet it in interviews or specialized numeric code.

The Master Theorem

A shortcut for recurrences of the form T(n) = a * T(n/b) + f(n).

a = number of subproblems
b = size reduction factor
f(n) = work to divide and combine

If f(n) = O(n^c) where c < log_b(a):   T(n) = Θ(n^log_b(a))
If f(n) = Θ(n^c) where c = log_b(a):   T(n) = Θ(n^c * log n)
If f(n) = Ω(n^c) where c > log_b(a):   T(n) = Θ(f(n))

Don't memorize the formulas; recognize the common cases:

  • T(n) = 2T(n/2) + O(n) → O(n log n). Merge sort.
  • T(n) = 2T(n/2) + O(1) → O(n). Tree traversal.
  • T(n) = T(n/2) + O(1) → O(log n). Binary search.
  • T(n) = T(n-1) + O(1) → O(n). Linear recursion.
  • T(n) = 2T(n-1) + O(1) → O(2^n). Naive Fibonacci.

Greedy vs DP vs Divide-and-Conquer

Pattern           Makes local      Reuses subproblem     Example
                  choices          solutions
Greedy            Yes              No                    Interval scheduling
DP                No (considers    Yes                   0/1 knapsack
                  all options)
Divide-and-       No               Rarely                Merge sort
conquer

A useful heuristic:

  • If you can make a local choice and prove it's correct → greedy.
  • If you need to consider multiple options and the same subproblems recur → DP.
  • If you can cleanly split into independent subproblems → divide-and-conquer.

In practice, greedy and DP are most commonly confused. Interview tip: if a greedy solution "seems right", try to find a counterexample. If you can, use DP. If you can't, try to prove greedy.

Common Pitfalls

Writing greedy without proof. If you can't explain why the greedy choice is optimal, be suspicious.

Mis-sorting for greedy. The sorting criterion is the key insight. Sort by end time for interval scheduling; value-per-weight for fractional knapsack; frequency for Huffman. Wrong criterion gives a wrong answer.

Using greedy when DP is needed. Coin change with non-canonical denominations, 0/1 knapsack, edit distance: these need DP.

Missing the recursion base case. Divide-and-conquer without a base case is infinite recursion. Always handle the smallest subproblem.

Copying inputs on each recurse. arr[:mid] slices the list (O(n)). For very large inputs, pass indices instead of slices.

Next Steps

Continue to 11-patterns.md for the repeated patterns behind most algorithm problems.