Greedy Algorithms

When the best local move is safe

A greedy algorithm makes the locally best choice at each step without revisiting it. It works when you can argue that some optimal solution starts with the greedy choice (an exchange argument). Jump game tracks the farthest reachable index; minimum jumps treats reachable ranges as BFS levels. When greedy fails (coin change with arbitrary coins), use dynamic programming instead.

Jump game and minimum jumps, run

I ran this with Python 3.12.3 (standard library only). The first array can reach the end and needs 2 jumps; the second gets stuck at the 0; all-ones needs 3 jumps for four positions.

# Greedy: can we reach the end? and the minimum number of jumps
def can_jump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + x)
    return True

def min_jumps(nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:                  # must jump to extend the range
            jumps, cur_end = jumps + 1, farthest
    return jumps

print(can_jump([2, 3, 1, 1, 4]), can_jump([3, 2, 1, 0, 4]))
print(min_jumps([2, 3, 1, 1, 4]), min_jumps([1, 1, 1, 1]))

Output:

True False
2 3

Test greedy against a counterexample

Before committing, try small tricky inputs; if greedy fails one, switch to DP.

Quick check: When is a greedy algorithm correct?

• Only when n is small
• Always
• Only for sorted inputs
• When a locally optimal choice can be shown to lead to a global optimum