Maximum Number of Consecutive Values You Can Make: Greedy Reachability

You are given an integer array coins of length n, where each element represents a coin denomination. You can pick any subset of the coins. Return the maximum number of consecutive integer values (starting from 0) that you can make with the selected coins.

This is LeetCode 1798: Maximum Number of Consecutive Values You Can Make, and it is one of the cleanest examples of a greedy problem that looks like it needs dynamic programming but does not.

Why this problem matters

At first glance, this looks like a subset-sum or knapsack variant. You have coins, you want to know which totals you can make, and the brute force approach would enumerate all 2^n subsets. That is exponential and completely impractical for large inputs.

The greedy approach solves it in O(n log n) time, which feels almost too good to be true. The trick is that you do not need to track which values are reachable. You only need to track how far the consecutive range extends from 0. Once you see this, the problem collapses into a simple sorted scan.

This pattern of "maintaining a reachable range" shows up in problems about patching arrays, covering intervals, and any scenario where you are building consecutive coverage from a set of building blocks.

The key insight

Sort the coins. Imagine you can already make every value in the range [0, reach]. Now you pick up the next coin with value c. If c is at most reach + 1, then by adding c to every value you could already make, you can now reach all values in [0, reach + c]. The range extends seamlessly because there is no gap.

But if c is greater than reach + 1, there is a gap. You cannot make reach + 1 no matter what you do with this coin or any larger coin. So you stop.

The algorithm:

1. Sort the coins in ascending order.
2. Initialize reach = 0 (you can always make value 0 with an empty subset).
3. For each coin c in sorted order: if c is <= reach + 1, set reach = reach + c. Otherwise, stop.
4. Return reach + 1.

The solution

def get_maximum_consecutive(coins: list[int]) -> int:
    coins.sort()
    reach = 0
    for c in coins:
        if c > reach + 1:
            break
        reach += c
    return reach + 1

Let's walk through what each piece does.

The sort ensures we process the smallest coins first. This is critical because small coins are the ones that fill gaps. If you processed a large coin before the small ones, you might think there is a gap when the small coins would have filled it.

The reach variable tracks the upper bound of the consecutive range [0, reach] that we can form. It starts at 0 because we can always make 0 (the empty subset).

For each coin c, the check c > reach + 1 asks: "Is this coin too large to connect to our current range?" If we can make [0, reach] and the coin is at most reach + 1, then adding c to every achievable sum gives us [c, reach + c]. Combined with the original [0, reach], we now cover [0, reach + c] with no gap.

If the coin exceeds reach + 1, we cannot make the value reach + 1. No future coin (which is at least as large) will help either. So we break.

Visual walkthrough

Let's trace through the example coins = [1, 1, 1, 4] step by step. Watch how the reachable range [0, reach] grows as each coin is processed.

Notice how the three 1-coins build the range up to [0, 3], and then the coin with value 4 is exactly small enough (4 <= 3 + 1) to extend the range all the way to [0, 7]. If that last coin had been 5 instead of 4, we would have stopped at reach = 3 with an answer of 4, because 5 > 3 + 1 leaves a gap at value 4.

Complexity analysis

Time is O(n log n) dominated by the sort. The single pass through the sorted array is O(n), so the total is O(n log n). This is dramatically better than the O(2^n) brute force.

Space is O(1) beyond the input (or O(n) if your sorting algorithm requires extra space). We only store the reach variable. No hash sets, no DP tables, no auxiliary arrays.

The building blocks

1. Greedy reachable range expansion

The core pattern of maintaining a reachable range and extending it with each element:

coins.sort()
reach = 0
for c in coins:
    if c > reach + 1:
        break
    reach += c

This pattern applies to any problem where you are trying to cover consecutive values starting from 0. The "Patching Array" problem (LeetCode 330) uses the exact same invariant: if the next number exceeds reach + 1, you need to patch the gap. The insight is identical. You only need to track the frontier, not the full set of reachable values.

2. Sort-first greedy strategy

The pattern of sorting input before applying a greedy rule:

items.sort()
for item in items:
    if can_extend(item):
        extend(item)
    else:
        break

Sorting is the enabler for many greedy algorithms. It lets you process elements in an order where a local decision (extend or stop) is guaranteed to be globally optimal. You see this in interval scheduling, activity selection, and any problem where processing in sorted order prevents you from missing a better choice later.

Edge cases

Before submitting, think through these scenarios:

• Empty coins array: no coins means you can only make 0. Return 1.
• All coins are 1: reach grows by 1 each step. Answer is n + 1.
• Smallest coin is greater than 1: the first coin exceeds 0 + 1 = 1, so you immediately stop. Return 1 (can only make 0).
• Single coin of value 1: reach becomes 1. Answer is 2 (values 0 and 1).
• Very large coins like [1, 2, 4, 8, ...]: powers of 2 cover all values up to 2^n - 1. This is the most efficient coverage possible.
• Duplicate coins: duplicates are fine. Each copy independently extends the range just like any other coin.

From understanding to recall

You have seen how sorting coins and tracking a reachable range gives you the answer in O(n log n) time. The logic is short and the code is minimal. But the insight that this greedy approach is correct, that you do not need subset enumeration or DP, is the part that needs to stick.

The detail that trips people up is the condition c > reach + 1. Why reach + 1 and not reach? Because reach is already reachable. The question is whether you can make reach + 1, the next value just beyond your current coverage. If the current coin is too large to bridge that gap, you are done. Getting this boundary condition right under time pressure requires practice, not just understanding.

Spaced repetition locks it in. You practice writing the sort, the loop, and the break condition from memory. After a few rounds, the pattern is automatic. You see "consecutive values from 0" and the greedy template comes out without hesitation.

Related posts

• Coin Change - The classic DP approach to coin problems, where you need exact amounts rather than consecutive coverage
• Combination Sum - Exploring all subsets that sum to a target, the backtracking approach this greedy avoids
• Subsets - The subset generation pattern that brute force would require here

CodeBricks breaks Maximum Number of Consecutive Values into its greedy reachable-range building block, then drills it with spaced repetition. You type the sort, the range check, and the break condition from scratch until the pattern is automatic. When a greedy coverage problem shows up in your interview, you do not think about it. You just write it.