Introduction

The Non-Constructible Change problem looks like a search problem at first, but the intended solution is greedy. The trick is not to test every sum. Instead, you keep track of the largest amount of change you can already build without gaps and ask whether the next coin extends that range.

Start with the right invariant

After sorting the coins, imagine you have processed some prefix of them. Suppose you can build every value from 1 up to current_change. That means there are no gaps in that interval.

Now consider the next coin:

• if the coin value is at most current_change + 1, you can extend the reachable interval
• if the coin value is larger than current_change + 1, then current_change + 1 is impossible to build

That second bullet is the whole greedy insight. If every processed coin only got you to current_change, and the next unused coin is too large to fill the next missing amount, nothing later can fix that gap because the remaining coins are even larger.

Why the greedy step is correct

Suppose you can construct every amount through 6, and the next sorted coin is 3. Then you can now construct every amount through 9:

• existing range: 1 through 6
• add the new coin to that range: 4 through 9

Together, those intervals cover 1 through 9 with no gap.

Now suppose instead the next coin is 8. You still cannot make 7. The new coin is too large, and all later coins are at least 8, so the missing amount stays missing forever. That means the answer is exactly 7.

This is why sorting matters. Without sorted order, you cannot safely reason that later coins will only be bigger.

Write the algorithm directly from the invariant

Once the invariant is clear, the code is short:

1def non_constructible_change(coins):
2    current_change = 0
3
4    for coin in sorted(coins):
5        if coin > current_change + 1:
6            return current_change + 1
7        current_change += coin
8
9    return current_change + 1
10
11
12print(non_constructible_change([5, 7, 1, 1, 2, 3, 22]))

If you run that example, the result is 20.

The time complexity is O(n log n) because of sorting. The loop itself is linear. Extra space is O(1) if the sort is in place, or O(n) if your language creates a new sorted copy.

Walk through a concrete example

Take the coins [1, 1, 3, 4].

1. Start with current_change = 0.
2. Read coin 1. Because 1 is not greater than 1, extend the reachable range to 1.
3. Read coin 1. Because 1 is not greater than 2, extend the range to 2.
4. Read coin 3. Because 3 is not greater than 3, extend the range to 5.
5. Read coin 4. Because 4 is not greater than 6, extend the range to 9.

You finished the list, so the smallest missing amount is 10.

Notice what the algorithm never does: it never enumerates all subsets, stores all achievable sums, or tries dynamic programming. Those approaches work, but they solve a more expensive problem than this prompt actually asks.

How to recognize this pattern in interviews

The reason many people get stuck is that the prompt sounds combinatorial. That usually triggers brute force or subset-sum thinking. A better question is this: what is the smallest amount I cannot cover yet, and what does the next smallest coin do to that boundary?

Once you phrase it that way, the invariant becomes natural:

• reachable amounts are continuous from 1 through current_change
• the next coin either preserves continuity or reveals the first gap

That is often how greedy proofs are found. You stop thinking about all solutions and instead track the boundary of what is already guaranteed.

Common Pitfalls

The biggest mistake is forgetting to sort first. Without sorted coins, the greedy argument breaks.

Another common error is using >= instead of >. If the next coin equals current_change + 1, that is good news, not failure, because it exactly fills the next missing value.

Some solutions also start from 1 instead of 0 for current_change. That shifts the invariant and creates off-by-one bugs.

Finally, avoid overcomplicating the problem with subset generation or dynamic programming unless the prompt has extra constraints that change the goal.

Summary

• Sort the coins and track the highest continuous amount you can already build.
• If the next coin is greater than current_change + 1, that next amount is the answer.
• If the next coin is small enough, extend the reachable range by adding it.
• The algorithm is greedy, correct, and runs in O(n log n) time.
• The key interview skill is spotting the invariant instead of exploring all combinations.