#1798

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Number of Consecutive Values You Can Make

Find the maximum number of consecutive integer values starting from zero that can be formed using your coins array.

Problem Statement

You are given an integer array coins representing n coins with positive integer values. You can use any subset of these coins to form sums, and your goal is to determine consecutive sums starting from 0.

Return the maximum number of consecutive integer values that can be formed beginning with 0. Multiple coins may share the same value, and the result must account for all possible consecutive sequences achievable using these coins.

Examples

Example 1

Input: coins = [1,3]

Output: 2

You can make the following values:

0: take []
1: take [1] You can make 2 consecutive integer values starting from 0.

Example 2

Input: coins = [1,1,1,4]

Output: 8

You can make the following values:

0: take []
1: take [1]
2: take [1,1]
3: take [1,1,1]
4: take [4]
5: take [4,1]
6: take [4,1,1]
7: take [4,1,1,1] You can make 8 consecutive integer values starting from 0.

Example 3

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

Output: 20

Example details omitted.

Constraints

coins.length == n
1 <= n <= 4 * 104
1 <= coins[i] <= 4 * 104

Solution Approach

Sort and Initialize

Begin by sorting the coins in ascending order. Initialize a variable maxConsecutive to 0 representing the largest consecutive value achievable so far starting from 0.

Iterate and Apply Greedy Invariant

For each coin value v in the sorted array, if v is less than or equal to maxConsecutive + 1, add it to extend the consecutive range: maxConsecutive += v. If v > maxConsecutive + 1, break, because a gap exists and further consecutive values cannot be formed immediately.

Return Result

After processing all coins, maxConsecutive will represent the maximum number of consecutive integer values that can be formed starting from 0. Return maxConsecutive + 1 to include 0.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n). Iterating through the coins is O(n), making total time O(n log n). Space is O(1) additional, or O(n) if sorting creates a copy.

What Interviewers Usually Probe

Candidate recognizes that sorting is necessary for the greedy invariant to work.
Candidate tracks the running maximum of consecutive values and correctly applies the extension rule.
Candidate notices that encountering a coin larger than maxConsecutive+1 stops consecutive formation.

Common Pitfalls or Variants

Common pitfalls

Not sorting the coins first breaks the greedy extension logic.
Miscounting maxConsecutive by off-by-one errors when including 0.
Attempting to use dynamic programming unnecessarily increases complexity and misses the greedy invariant insight.

Follow-up variants

Coins with duplicates only: test the greedy extension with multiple identical coins.
Limited coin values: adjust the approach when the largest coin is significantly bigger than previous sums.
Find non-consecutive maximum sum sequences: analyze failure modes when gaps exist in coin values.

FAQ

What is the key pattern in Maximum Number of Consecutive Values You Can Make?

The core pattern is a greedy choice plus invariant validation: if all values up to x are formable, adding coin v extends the range to x+v.

Why do we sort the coins before processing?

Sorting ensures we always add the smallest available coin to extend consecutive sums without skipping values, maintaining the invariant.

Can we use dynamic programming instead of greedy?

Dynamic programming works but is unnecessary; it increases time and space complexity while the greedy invariant directly computes the answer.

How do duplicates affect the solution?

Duplicates naturally extend the consecutive range. Each coin is considered in order, so repeated values simply add to maxConsecutive when applicable.

What happens if a coin value is larger than maxConsecutive+1?

A gap is created, and the consecutive sequence stops. No further consecutive sums can be formed from this point without smaller coins.

terminal

Solution

Solution 1: Sorting + Greedy

First, we sort the array. Then we define $ans$ as the current number of consecutive integers that can be constructed, initialized to $1$.

1

2

3

4

5

6

7

8

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        ans = 1
        for v in sorted(coins):
            if v > ans:
                break
            ans += v
        return ans

Continue Practicing

#1833 maximum ice cream bars #1838 frequency of the most frequent element #1846 maximum element after decreasing and rearranging