Problem Description

You have an integer array coins of length n, where each element represents the value of a coin you own. You can select any subset of these coins to create a sum equal to some value x.

Your task is to find the maximum number of consecutive integers that you can create, starting from and including 0.

For example, if you can create the values 0, 1, 2, 3, 4, then the answer would be 5 (since you can make 5 consecutive integers starting from 0).

Note that you may have multiple coins with the same value.

The solution works by sorting the coins first, then greedily checking if each coin can extend our current range of consecutive integers. We maintain a variable ans that represents how many consecutive integers we can currently make (starting from 0).

For each coin value v in sorted order:

• If v > ans, we've found a gap - we cannot make the value ans, so we stop
• Otherwise, if we can already make values [0, ans-1], adding coin v allows us to make all values in [0, ans-1] plus [v, v+ans-1], effectively extending our range to [0, ans+v-1]

The algorithm returns the total count of consecutive integers that can be formed starting from 0.

Intuition

The key insight is to think about what range of consecutive integers we can construct at each step. Let's say we can currently make all integers from [0, k-1]. What happens when we add a new coin with value v?

If v ≤ k, then we can use this coin to extend our range. Why? Because:

• We can already make 0, 1, 2, ..., k-1
• Adding coin v means we can also make v, v+1, v+2, ..., v+(k-1)
• Since v ≤ k, these two ranges overlap and merge into one continuous range [0, k+v-1]

However, if v > k, we have a problem. We can't make the value k because:

• Without using coin v, we can only make up to k-1
• Using coin v gives us at minimum v, which is already greater than k
• This creates a gap at value k that we cannot fill

This naturally leads to a greedy approach: sort the coins in ascending order and try to use each coin to extend our current range. Starting with the range [0, 0] (we can make 0 by selecting no coins), we process each coin:

• If the coin value is small enough (v ≤ current_max + 1), we can extend our range
• If the coin value is too large (v > current_max + 1), we've found the limit of consecutive integers we can make

The sorting is crucial because using smaller coins first maximizes our ability to create consecutive integers without gaps. Larger coins are more likely to create gaps if used too early.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a sorting + greedy strategy:

1. Sort the coins array: We sort the coins array in ascending order using sorted(coins). This ensures we process smaller valued coins first, which is essential for building consecutive integers without gaps.

2. Initialize the answer: We set ans = 1, which represents that initially we can make exactly 1 consecutive integer (just 0 by selecting no coins).

3. Iterate through sorted coins: For each coin value v in the sorted array:

   • Check if we can extend our range: If v > ans, it means we cannot construct the value ans. This is because:
     • Without using coin v, we can make values [0, ans-1]
     • Using coin v would give us at minimum the value v, which is already greater than ans
     • Therefore, we have a gap at ans that cannot be filled
   • Break if gap found: When v > ans, we immediately break and return ans as our answer
   • Extend the range: If v ≤ ans, we can use this coin to extend our range. We update ans += v, meaning we can now make all consecutive integers from 0 to ans + v - 1

4. Return the result: After processing all coins (or breaking early), ans represents the maximum number of consecutive integers we can make starting from 0.

The time complexity is O(n log n) due to sorting, where n is the number of coins. The space complexity is O(1) if we don't count the space used for sorting.

The algorithm works because at each step, ans maintains the invariant that we can create all integers in the range [0, ans-1]. When we add a coin of value v where v ≤ ans, we can create all values in [0, ans-1] (without the coin) and [v, v+ans-1] (with the coin), which together form the continuous range [0, ans+v-1].

Example Walkthrough

Let's walk through a concrete example with coins = [1, 1, 4, 7].

Step 1: Sort the coins

• Sorted array: [1, 1, 4, 7]
• Initialize ans = 1 (we can make consecutive integers [0] by selecting no coins)

Step 2: Process first coin (value = 1)

• Check: Is 1 > 1? No, so we can use this coin
• Before this coin: we can make [0] (range [0, 0])
• With this coin: we can also make [1]
• Combined range: [0, 1]
• Update: ans = 1 + 1 = 2 (we can now make 2 consecutive integers: 0 and 1)

Step 3: Process second coin (value = 1)

• Check: Is 1 > 2? No, so we can use this coin
• Before this coin: we can make [0, 1]
• With this coin: we can make [1, 2] (add 1 to each value we could make before)
• Combined range: [0, 2]
• Update: ans = 2 + 1 = 3 (we can now make 3 consecutive integers: 0, 1, and 2)

Step 4: Process third coin (value = 4)

• Check: Is 4 > 3? Yes! This means we have a gap
• Without this coin: we can make [0, 2]
• With this coin: minimum value we can make is 4 (using just this coin)
• We cannot make the value 3, so we stop here

Result: Return ans = 3

We can verify this is correct:

• Value 0: select no coins
• Value 1: select the first coin with value 1
• Value 2: select both coins with value 1
• Value 3: cannot be made (gap exists here)

Therefore, the maximum number of consecutive integers starting from 0 is 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The dominant operation in this code is the sorted() function, which sorts the coins array. Python's built-in sorting algorithm (Timsort) has a time complexity of O(n × log n) where n is the length of the array. After sorting, the code iterates through the sorted array once, which takes O(n) time. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(log n)

The sorted() function in Python uses Timsort, which requires O(log n) space for the recursive call stack in the worst case. The sorted array itself is stored in a new list, but when analyzing space complexity for sorting algorithms, we typically focus on the auxiliary space used by the sorting process itself, which is O(log n). The remaining variables (ans and v) use constant space O(1). Therefore, the overall space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Sort the Array

One of the most common mistakes is processing the coins in their original order instead of sorting them first. The greedy approach only works when we process coins from smallest to largest.

Incorrect approach:

def getMaximumConsecutive(self, coins: List[int]) -> int:
    max_consecutive = 1
    # Processing coins without sorting - WRONG!
    for coin_value in coins:
        if coin_value > max_consecutive:
            break
        max_consecutive += coin_value
    return max_consecutive

Why it fails: Consider coins = [1, 4, 10, 3, 1]. Without sorting, we would process 1 (get range [0,1]), then 4 (cannot use it since 4 > 2), and stop. But if sorted as [1, 1, 3, 4, 10], we can make [0,9].

2. Incorrect Initial Value

Starting with max_consecutive = 0 instead of 1 is a subtle but critical error.

Incorrect initialization:

def getMaximumConsecutive(self, coins: List[int]) -> int:
    max_consecutive = 0  # WRONG! Should be 1
    sorted_coins = sorted(coins)
    for coin_value in sorted_coins:
        if coin_value > max_consecutive:
            break
        max_consecutive += coin_value
    return max_consecutive

Why it fails: With max_consecutive = 0, the first coin would always satisfy coin_value > 0, causing immediate termination. We'd return 0 even when we could form consecutive integers.

3. Misunderstanding the Return Value

Some might think we need to return max_consecutive - 1 (the maximum value we can create) instead of max_consecutive (the count of consecutive integers).

Incorrect return:

def getMaximumConsecutive(self, coins: List[int]) -> int:
    max_consecutive = 1
    sorted_coins = sorted(coins)
    for coin_value in sorted_coins:
        if coin_value > max_consecutive:
            break
        max_consecutive += coin_value
    return max_consecutive - 1  # WRONG! Should return max_consecutive

Why it fails: The problem asks for the count of consecutive integers starting from 0. If we can make [0, 1, 2, 3], that's 4 integers, not 3.

4. Using <= Instead of < in the Break Condition

Using the wrong comparison operator can cause premature termination.

Incorrect comparison:

def getMaximumConsecutive(self, coins: List[int]) -> int:
    max_consecutive = 1
    sorted_coins = sorted(coins)
    for coin_value in sorted_coins:
        if coin_value >= max_consecutive:  # WRONG! Should be >
            break
        max_consecutive += coin_value
    return max_consecutive

Why it fails: When coin_value == max_consecutive, we can still use this coin to extend our range. For example, if we can make [0,2] and have a coin of value 3, we can extend to make [0,5].

Solution to Avoid These Pitfalls:

1. Always sort the array first
2. Initialize with max_consecutive = 1 (representing that we can make 0)
3. Use strict inequality coin_value > max_consecutive for the break condition
4. Return max_consecutive directly as it represents the count of consecutive integers