LeetCode Problem 1798

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

LeetCode 1798 - Maximum Number of Consecutive Values You Can Make

Problem Understanding

The problem gives us an array of coin values, where each coin can be used at most once. We are asked to determine the maximum number of consecutive integer values that can be formed starting from 0.

More specifically, if the answer is k, that means we can form every integer value in the range:

[0, k - 1]

but we cannot form the value k.

The important detail is that the sequence must start at 0 and remain consecutive without gaps. Even if we can form large values later, a missing smaller value breaks the sequence.

For example, if we can form:

0, 1, 2, 3, 5

then the answer is 4, because the consecutive sequence stops before 4.

The input array can contain duplicate values, and the order of coins in the input does not matter because we are free to choose any subset of coins.

The constraints are important:

• 1 <= n <= 4 * 10^4
• 1 <= coins[i] <= 4 * 10^4

A brute-force subset enumeration would require checking up to 2^n subsets, which is completely infeasible for n = 40000.

This strongly suggests that the problem requires a greedy or mathematical observation rather than explicit subset generation.

Several edge cases are important to recognize immediately:

• Arrays without a 1, such as [2,3,4]

• We can only form 0, so the answer is 1

• Arrays with many duplicate 1s

• These extend the consecutive range gradually

• Arrays with large gaps

• A gap larger than the currently reachable range immediately stops expansion

• Single-element arrays

• [1] gives answer 2

• [5] gives answer 1

Understanding why gaps matter is the key insight behind the optimal greedy solution.

Approaches

Brute Force Approach

A brute-force solution would generate every possible subset of coins and compute all achievable sums.

For each subset:

1. Compute the subset sum
2. Store the sum in a set
3. After processing all subsets, start from 0 and check how many consecutive integers exist

This works because every achievable value is explicitly computed.

However, the number of subsets is:

2^n

which becomes astronomically large even for modest values of n.

For example:

n = 40

already produces more than one trillion subsets.

Since the actual constraint is 40000, brute force is impossible.

Optimal Greedy Approach

The key observation is surprisingly elegant.

Suppose we have already processed some coins and can currently form every value in the range:

[0, reachable]

Now consider the next smallest coin value coin.

There are two cases:

Case 1: coin <= reachable + 1

Then we can extend the reachable range.

Why?

Because:

• We can already form every value from 0 to reachable
• Adding coin to each of those values creates:

[coin, reachable + coin]

Since coin <= reachable + 1, there is no gap between the old range and the new range.

So the new reachable range becomes:

[0, reachable + coin]

Case 2: coin > reachable + 1

Then we have found a gap.

We cannot form:

reachable + 1

because:

• All previous sums are at most reachable
• The new coin is too large to bridge the gap

At that point, expansion becomes impossible, and we stop.

This greedy property only works correctly if the coins are processed in sorted order.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(2^n)	Enumerates all subsets and sums
Optimal Greedy	O(n log n)	O(1) or O(log n)	Sorts coins and greedily expands reachable range

Algorithm Walkthrough

1. Sort the coins array in ascending order.

Sorting ensures we process smaller coins first. This is essential because the greedy proof depends on knowing the smallest remaining coin at every step. 2. Initialize a variable reachable = 0.

This means we can currently form all values in the range:

[0, reachable]

Initially, only 0 is achievable using no coins. 3. Iterate through each coin in sorted order. 4. For each coin, check whether:

coin <= reachable + 1

If true, the coin can extend the reachable range continuously. 5. If the condition is true, update:

reachable += coin

This means we can now form all values up to the new maximum. 6. If the condition is false, stop immediately.

We have discovered a gap at:

reachable + 1

and no future larger coin can fix it. 7. Return:

reachable + 1

because the number of consecutive values starting from 0 equals the size of the range:

[0, reachable]

Why it works

The invariant is:

Before processing each coin, we can form every value in [0, reachable].

If the next coin is at most reachable + 1, then combining that coin with previously reachable sums fills the range continuously without gaps.

If the next coin exceeds reachable + 1, then the value reachable + 1 is impossible to form, because all existing sums are too small and all future coins are even larger.

Therefore, the greedy expansion is both safe and optimal.

Python Solution

from typing import List

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        coins.sort()

        reachable = 0

        for coin in coins:
            if coin > reachable + 1:
                break

            reachable += coin

        return reachable + 1

The implementation begins by sorting the coins so that smaller values are processed first. This ordering is critical for maintaining the greedy invariant.

The variable reachable tracks the maximum consecutive value we can currently form starting from 0.

During iteration, each coin is checked against reachable + 1.

If the coin is small enough, it extends the reachable interval continuously. We update reachable by adding the coin value.

If the coin is too large, a gap appears, and the loop terminates immediately because no later coin can repair the missing value.

Finally, the method returns reachable + 1, which represents the total count of consecutive values starting from 0.

Go Solution

package main

import "sort"

func getMaximumConsecutive(coins []int) int {
	sort.Ints(coins)

	reachable := 0

	for _, coin := range coins {
		if coin > reachable+1 {
			break
		}

		reachable += coin
	}

	return reachable + 1
}

The Go implementation follows the exact same greedy logic as the Python version.

The main difference is that Go uses sort.Ints() for sorting and iterates through the slice using a range loop.

Integer overflow is not a concern here because the maximum possible total sum is:

40000 * 40000 = 1.6 * 10^9

which still fits safely inside a 32-bit signed integer, and Go's int type is typically 64-bit on modern systems.

An empty slice is not possible because the constraints guarantee at least one coin.

Worked Examples

Example 1

coins = [1,3]

After sorting:

[1,3]

Coin	Reachable Before	Condition	Reachable After
1	0	1 <= 1, true	1
3	1	3 <= 2, false	stop

We can form:

0, 1

but cannot form 2.

Answer:

2

Example 2

coins = [1,1,1,4]

Already sorted.

Coin	Reachable Before	Condition	Reachable After
1	0	1 <= 1, true	1
1	1	1 <= 2, true	2
1	2	1 <= 3, true	3
4	3	4 <= 4, true	7

We can form every value in:

[0,7]

Total consecutive values:

8

Example 3

coins = [1,4,10,3,1]

After sorting:

[1,1,3,4,10]

Coin	Reachable Before	Condition	Reachable After
1	0	1 <= 1, true	1
1	1	1 <= 2, true	2
3	2	3 <= 3, true	5
4	5	4 <= 6, true	9
10	9	10 <= 10, true	19

We can form every value in:

[0,19]

Total consecutive values:

20

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on sorting implementation

The iteration itself is linear, requiring only one pass through the sorted array.

The dominant cost comes from sorting, which requires O(n log n) time.

The algorithm uses only a few extra variables beyond the input array. Depending on the language's sorting implementation, recursion stack usage may introduce O(log n) auxiliary space.

Test Cases

from typing import List

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        coins.sort()

        reachable = 0

        for coin in coins:
            if coin > reachable + 1:
                break

            reachable += coin

        return reachable + 1

sol = Solution()

assert sol.getMaximumConsecutive([1, 3]) == 2
# Basic gap case

assert sol.getMaximumConsecutive([1, 1, 1, 4]) == 8
# Multiple ones gradually extend the range

assert sol.getMaximumConsecutive([1, 4, 10, 3, 1]) == 20
# Example with sorting and large extension

assert sol.getMaximumConsecutive([2]) == 1
# Cannot form 1 because smallest coin is too large

assert sol.getMaximumConsecutive([1]) == 2
# Single usable coin

assert sol.getMaximumConsecutive([1, 2, 5]) == 4
# Gap appears after forming 0 to 3

assert sol.getMaximumConsecutive([1, 1, 2, 2]) == 7
# Continuous expansion without gaps

assert sol.getMaximumConsecutive([5, 7, 9]) == 1
# No coin with value 1

assert sol.getMaximumConsecutive([1, 1, 1, 1, 1]) == 6
# Many duplicate ones

assert sol.getMaximumConsecutive([1, 2, 3, 4, 5]) == 16
# Entire range expands continuously

print("All tests passed.")

Test	Why
[1,3]	Verifies early gap detection
[1,1,1,4]	Verifies continuous range extension
[1,4,10,3,1]	Verifies sorting and greedy expansion
[2]	Verifies behavior without coin 1
[1]	Smallest valid successful case
[1,2,5]	Verifies stopping after a gap
[1,1,2,2]	Verifies cumulative merging of ranges
[5,7,9]	Verifies immediate failure case
[1,1,1,1,1]	Verifies many duplicates
[1,2,3,4,5]	Verifies full uninterrupted expansion

Edge Cases

One important edge case occurs when the array does not contain a coin with value 1. For example:

[2,3,4]

Since we cannot form the value 1, the consecutive sequence immediately stops at 0. A buggy implementation might incorrectly assume larger coins can still contribute meaningfully, but the greedy condition correctly detects the gap immediately.

Another important case involves duplicate small coins, especially many 1s. For example:

[1,1,1,1]

Each additional 1 increases the reachable range by exactly one. Incorrect implementations sometimes fail to recognize that repeated values continue extending the interval continuously. The greedy invariant handles duplicates naturally.

A third critical edge case involves a large gap after some successful expansion. Consider:

[1,2,10]

After processing 1 and 2, we can form all values from 0 to 3. However, the next coin is 10, which is larger than reachable + 1 = 4. Since 4 cannot be formed, the algorithm must stop immediately. Future larger coins cannot repair the missing value because the array is sorted.

A final subtle edge case is already sorted versus unsorted input. The algorithm fundamentally depends on processing coins in ascending order. Without sorting, the greedy property breaks. For example:

[4,1,2]

If processed in this order, we would incorrectly stop at the first coin. Sorting transforms it into:

[1,2,4]

which allows continuous expansion up to 7.