When one element has no options

Tip

Handle all copies of a value at once

If a value appears three times, all three must start runs, and those runs are identical. Processing them one at a time repeats the same work; subtracting the whole count in one go is both faster and easier to reason about.

That is why the inner loop subtracts needed rather than one. Whenever a greedy step applies uniformly to a group, doing the group at once usually simplifies the code as well as the complexity.

Tip

The cheap impossibility check first

If the count does not divide evenly by the run size, no arrangement exists and nothing else needs computing. Cheap global checks before the main work are the same habit as the total check in the last lesson.

It also guards the main loop from a class of inputs where a partial run would otherwise be silently accepted.

Gotcha

Iterate the distinct values in order, not the raw input

The argument depends on always taking the smallest remaining value. Iterating the original list in its given order breaks that and the forced-choice justification no longer applies.

Sorting the distinct values and skipping those already consumed is what implements smallest-remaining correctly. Skipping zero counts matters, since a value fully consumed by earlier runs must not start a new one.

Tip

A heap is the alternative

A min-heap of the remaining values gives the smallest at each step without sorting up front, which is preferable when values arrive over time rather than all at once.

For a fixed input, sorting once is simpler and the same complexity. Knowing which one the situation calls for is the Unit 9 lesson applied here.

Cost

Cost

Counting is linear, sorting the distinct values is O(d log d), and the double loop touches each distinct value once per run offset, so O(d times size) overall.

In the worst case that is O(n log n) dominated by the sort. State it that way rather than as the double loop, since the sort is what actually dominates.