More greedy classics

Jump game: track the farthest reach

nums[i] is the longest jump you can make from index i. Starting at index 0, can you reach the last index? Trying every jump path is exponential. Instead, walk left to right and keep reach, the farthest index you can get to so far. If you ever stand on an index beyond reach, you are stuck. Otherwise update reach = max(reach, i + nums[i]). One pass: O(n) time and O(1) space.

def can_jump(nums):
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False           # this index cannot be reached
        reach = max(reach, i + step)
    return True

print(can_jump([2, 3, 1, 1, 4]), can_jump([3, 2, 1, 0, 4]))   # Output: True False

Gas station: restart after a deficit

Stations stand on a circular road. Station i gives gas[i] litres, and driving to the next station costs cost[i]. Starting with an empty tank, from which station can you drive the full circle? Two facts give an O(n) answer. First, if total gas < total cost, no start works. Second, if you start at s and the tank goes negative on reaching station j + 1, then NO station between s and j can be a start either: each of them would arrive at j with even less fuel. So jump the start to j + 1 and reset the tank.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start, tank = i + 1, 0
    return start

print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   # Output: 3

Boats to save people: two pointers plus greedy

Each boat carries at most two people with total weight ≤ limit. What is the fewest boats? Sort the weights. The heaviest person needs a boat anyway; the best partner for them is the lightest person, because if even the lightest cannot fit, nobody can. So pair the two ends when they fit, otherwise send the heaviest alone, and move the pointers inward. Sorting costs O(n log n) and the pass O(n).

def boats(people, limit):
    people = sorted(people)
    i, j, count = 0, len(people) - 1, 0
    while i <= j:
        if people[i] + people[j] <= limit:
            i += 1                 # the lightest goes with the heaviest
        j -= 1                     # the heaviest always leaves
        count += 1
    return count

print(boats([3, 2, 2, 1], 3), boats([3, 5, 3, 4], 5))   # Output: 3 4

Fractional knapsack: greedy works

A knapsack (bag) can carry capacity kilos. Each item has a value and a weight, and you may take any FRACTION of an item, like rice or spices sold loose. Sort items by value per kilo, highest first, and fill the bag in that order, taking a fraction of the last item that does not fit whole. The exchange argument: if an answer uses a kilo of a worse item while some of a better one is left, swapping that kilo raises the value. O(n log n).

def fractional(items, capacity):        # items: (value, weight)
    total = 0.0
    for value, weight in sorted(items, key=lambda it: it[0] / it[1], reverse=True):
        if capacity == 0:
            break
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
    return round(total, 2)

print(fractional([(60, 10), (100, 20), (120, 30)], 50))   # Output: 240.0

0/1 knapsack: greedy fails

If each item must be taken whole or not at all (a laptop, a phone), the same greedy rule breaks. With the items above and capacity 50, greedy by value per kilo takes the 10 kg and 20 kg items for 160 and then the 30 kg item does not fit. The best answer is the 20 kg and 30 kg items for 220. The 0/1 knapsack needs dynamic programming, which tries both "take" and "skip" for every item (Module 11).

Huffman coding: merge the two rarest

Huffman coding compresses text by giving frequent characters short bit codes and rare ones long codes. Put every character in a min-heap by frequency. Repeatedly pop the two rarest, join them under a new node whose frequency is their sum, and push it back. When one node is left, the path from it to each character gives that character's code, so characters merged early (the rare ones) end up deep, with long codes. Each of the n − 1 merges is O(log n): O(n log n). Formats such as ZIP's DEFLATE use Huffman codes as one step.

import heapq

def huffman_lengths(freq):
    heap = [(f, i, {ch: 0}) for i, (ch, f) in enumerate(freq.items())]
    heapq.heapify(heap)
    counter = len(heap)
    while len(heap) > 1:
        f1, _, a = heapq.heappop(heap)
        f2, _, b = heapq.heappop(heap)
        merged = {ch: depth + 1 for ch, depth in {**a, **b}.items()}
        heapq.heappush(heap, (f1 + f2, counter, merged))
        counter += 1
    return dict(sorted(heap[0][2].items()))

print(huffman_lengths({"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}))
# Output: {'a': 1, 'b': 3, 'c': 3, 'd': 3, 'e': 4, 'f': 4}

Common mistakes

• Jump game: returning True as soon as one jump looks good, or using BFS over all paths. Fix: one pass with the farthest reach.
• Gas station: trying every start, which is O(n²). Fix: total check plus the restart rule.
• Boats: pairing the two lightest people first. That can waste capacity. Fix: always handle the heaviest, paired with the lightest if they fit.
• Using the fractional greedy for the 0/1 knapsack. Fix: greedy only when items can be split; DP otherwise.
• Dividing by a weight of 0, or sorting by value instead of value per kilo. Fix: check the input and sort by value / weight.