When one element has no options

The strongest kind of greedy argument: the choice is not best, it is the only one available.

Key idea

Find the element with no freedom

Exchange arguments justify choices that could have gone another way. Some problems have a stronger property: one element has exactly one possible role, so no argument is needed at all.

Look for it. When every value must be grouped into consecutive runs of a fixed size, the smallest remaining value cannot be in the middle or at the end of any run, because that would require something smaller that does not exist. It must start a run.

That is forced, not chosen. Everything else follows by repetition.

Below, the smallest remaining value is taken twice in a row, and each time the run it is forced to start is removed from the counts.

1from collections import Counter2 3counts = Counter([1, 2, 3, 6, 2, 3, 4, 7, 8])4size = 35 6for _ in range(2):7    value = min(v for v in counts if counts[v] > 0)8    needed = counts[value]9    run = [value + offset for offset in range(size)]10    print(f"{value} must start {needed} run(s):", run)11    for following in run:12        counts[following] -= needed13    print("   left:", sorted(counts.elements()))

Nothing was decided at either step. The smallest value had exactly one place it could go.

Predict the output· 5 min

Predict the output: the value with no choices

Given a multiset that must be split into runs of consecutive values, the smallest remaining value is examined. Type the three lines it prints.

Python

1from collections import Counter2 3counts = Counter([1, 2, 3, 2, 3, 4])4size = 35value = min(counts)6 7print("smallest remaining:", value)8print("could it sit in the middle of a run?", counts[value - 1] > 0)9print("so it must start one, needing:", [value + offset for offset in range(size)])

Printed output

Problem· 26 min

Hand Of Straights

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1from collections import Counter2 3counts = Counter([1, 2, 3, 6, 2, 3, 4, 7, 8])4size = 35 6for _ in range(2):7 value = min(v for v in counts if counts[v] > 0)8 needed = counts[value]9 run = [value + offset for offset in range(size)]10 print(f"{value} must start {needed} run(s):", run)11 for following in run:12 counts[following] -= needed13 print(" left:", sorted(counts.elements()))

1from collections import Counter2 3counts = Counter([1, 2, 3, 2, 3, 4])4size = 35value = min(counts)6 7print("smallest remaining:", value)8print("could it sit in the middle of a run?", counts[value - 1] > 0)9print("so it must start one, needing:", [value + offset for offset in range(size)])