Greedy Algorithms

A Greedy Algorithm makes the locally optimal choice at each step and never revisits past decisions. Unlike DP, it does not explore all possibilities — it commits immediately. Greedy works when local optimality guarantees global optimality.

Problem: Best Time to Buy and Sell Stock

Given daily prices, find the maximum profit from one buy-sell transaction.

Greedy insight: buy at the lowest price seen so far, and at each day compute the profit if we sell today.

def max_profit(prices: list[int]) -> int:
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)          # update running minimum
        max_profit = max(max_profit, price - min_price)   # best profit so far

    return max_profit

One pass, $O(N)$ time. No DP table needed because the greedy choice (track the minimum) is always correct.

Problem: Jump Game

Given an array where each element is the maximum jump length from that position, can you reach the last index?

Greedy insight: track the furthest reachable position. If you can reach i, you can reach everything up to i + nums[i].

def can_jump(nums: list[int]) -> bool:
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False   # i is unreachable
        max_reach = max(max_reach, i + jump)
    return True

Greedy vs. Dynamic Programming

	Greedy	Dynamic Programming
Decision making	Commit to the best current option	Explore all options, pick the best
Correctness	Only works when local opt = global opt	Always correct (for DP-solvable problems)
Speed	Usually $O(N)$ or $O(N \log N)$	Often $O(N^2)$ or $O(N \cdot K)$
When to use	Exchange argument or matroid structure	Overlapping subproblems

Proving Greedy Correctness

Before coding a greedy solution, convince yourself it works with an exchange argument:

Suppose the optimal solution makes a different choice at step $k$ . Show that swapping its choice for the greedy choice produces a solution that is at least as good.

If you can make that argument, greedy is correct.

When Do I Use This?

Problems with interval scheduling, minimum spanning trees, or Huffman encoding.
Keywords: "minimum", "maximum", "feasible", and the constraint structure is simple enough that local choices dominate.
When DP would work but seems unnecessarily complex — check if greedy suffices.

Practice Problems

Done	Question	Difficulty
	Best Time to Buy and Sell Stock	Easy
	Gas Station	Medium
	Jump Game	Medium
	Jump Game II	Medium
	Partition Labels	Medium