Maximum Number of Consecutive Values You Can Make

Medium

Asked by:

20 views

Topics:

Greedy AlgorithmsArrays

You are given an integer array coins of length n which represents the n coins that you own. The value of the i^th coin is coins[i]. You can make some value x if you can choose some of your n coins such that their values sum up to x.

Return the maximum number of consecutive integer values that you can make with your coins starting from and including 0.

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

Example 1:

Input: coins = [1,3]
Output: 2
Explanation: 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
Explanation: 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

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can the input array contain zero or negative numbers?
Are there duplicate values allowed in the input array, and if so, how should they be handled?
If no consecutive sequence can be formed starting from 1, what should I return?
What is the maximum size of the input array?

Brute Force Solution

Approach

The brute force approach to this problem involves systematically trying out every possible combination of values to see which ones we can create. We start from a base value and then explore if we can reach the next consecutive value by adding one or more of the given numbers. This process repeats until we find the maximum range of consecutive values we can make.

Here's how the algorithm would work step-by-step:

Start with zero, assuming we can always make that value.
Consider each number we have. For each number, go through all the values we can already make.
For each value we can already make, try adding the new number to it. This gives us a new possible value.
Repeat this process for all the numbers we have, adding them to all the values we can make up to that point.
Keep track of all the new values we can make. After considering all the numbers, find the largest consecutive range of values starting from zero that we can create.

Code Implementation

def max_consecutive(coins):
    reachable_values = {0}
    
    # Iterate through each coin value provided
    for coin in coins:
        new_reachable_values = set()
        
        # Iterate through the current reachable values
        for reachable_value in reachable_values:

            # Add the current coin value to each reachable value.
            new_value = reachable_value + coin
            new_reachable_values.add(new_value)

        # Update reachable values with the newly formed values
        reachable_values.update(new_reachable_values)

    # Find the maximum consecutive length from 0.
    max_consecutive_length = 0
    while max_consecutive_length in reachable_values:

        # Count consecutive values starting from 0.
        max_consecutive_length += 1

    return max_consecutive_length

Big(O) Analysis

Time Complexity

O(n*m) – The outer loop iterates through each of the n numbers in the input array. The inner loop iterates through all the values we can already make, up to the maximum value m we can potentially create which depends on the sum of input elements. The addition operation inside the inner loop takes constant time. Therefore, the time complexity is approximately O(n * m), where n is the number of input values and m is the maximum achievable value (related to the sum of the input array).

Space Complexity

O(S) – The described solution keeps track of all the new values we can make, which can grow significantly depending on the input numbers. This set of values, which we'll call 'S', represents the auxiliary space required. In the worst-case scenario, 'S' could be quite large if the input numbers allow us to create a large range of consecutive values, up to the sum of all the input numbers. Therefore, the space complexity is O(S), where S represents the maximum possible sum we can make using the numbers.

Optimal Solution

Approach

We want to find the largest range of consecutive numbers we can make, starting from 0, using a given set of coin values. The key idea is to build the range iteratively, extending it as much as possible with each coin. Sorting the coins makes this process much easier and more efficient.

Here's how the algorithm would work step-by-step:

First, sort the coin values from smallest to largest. This allows us to build the consecutive range in an organized way.
Start with the ability to make the value 0 (our initial consecutive range).
Now, go through each coin value, one at a time, in the sorted order.
For each coin, check if adding it to our current range would create a gap. Specifically, see if the coin's value is bigger than one more than the largest value we can currently make.
If the coin's value is too big (creates a gap), we stop because we can't extend the range consecutively anymore.
If the coin's value is small enough (doesn't create a gap), we add the coin's value to our current largest value, extending the range.
Continue this process until we run out of coins or encounter a coin that creates a gap.
The final largest value we reached plus one represents the maximum number of consecutive values we can make starting from zero.

Code Implementation

def max_consecutive(coins):
    coins.sort()

    reachable_value = 0

    # Iterate through the sorted coins to extend the range
    for coin in coins:
        # If the current coin creates a gap, we can't extend
        if coin > reachable_value + 1:
            break

        reachable_value += coin

    # The maximum number of consecutive values is the reachable value + 1
    return reachable_value + 1

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input array of n coin values. Sorting algorithms like merge sort or quicksort typically have a time complexity of O(n log n). The subsequent loop iterates through the sorted array once, performing a constant-time check for each coin. Therefore, the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The algorithm primarily uses a few variables to store the current largest value that can be made and to iterate through the sorted coin values. The sorting operation, if done in place, doesn't contribute to auxiliary space. Therefore, the extra space required remains constant regardless of the number of coins, denoted as N. Hence, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input coins array	Return 0, as no values can be made without any coins.
Single coin with value 0	Return 1, as you can always make the value 0.
Coins array with negative values	The problem is defined for positive coin values; filter out or reject negative values as invalid input.
Coins array with very large positive values that can cause integer overflow when summing.	Use a data type that can accommodate large sums (e.g., long in Java/C++) or check for potential overflows before performing additions, returning the maximum representable value if overflow is imminent.
Coins array with all identical values (e.g., [1, 1, 1, 1])	The sorted sum will increment by the coin value at each iteration correctly.
Coins array with extremely skewed distribution, where the largest value is much greater than the sum of all others.	Sorting allows identifying this skew early, but the algorithm should still correctly iterate, summing until it reaches the point where consecutive sums are no longer possible.
Large input array to check for efficiency, e.g. an array containing 10000 values.	The solution's time complexity should ideally be O(n log n) due to sorting, and large inputs should be handled efficiently within reasonable time limits.
Array that already allows forming 0, 1, 2, ..., k and a coin value of k+2 is added.	The next consecutive number that can be made is k+1, so the result should still be k+1 even with the k+2 coin.

Empty input coins array

How to Handle:

Return 0, as no values can be made without any coins.

Single coin with value 0

How to Handle:

Return 1, as you can always make the value 0.

Coins array with negative values

How to Handle:

The problem is defined for positive coin values; filter out or reject negative values as invalid input.

Coins array with very large positive values that can cause integer overflow when summing.

How to Handle:

Use a data type that can accommodate large sums (e.g., long in Java/C++) or check for potential overflows before performing additions, returning the maximum representable value if overflow is imminent.

Coins array with all identical values (e.g., [1, 1, 1, 1])

How to Handle:

The sorted sum will increment by the coin value at each iteration correctly.

Coins array with extremely skewed distribution, where the largest value is much greater than the sum of all others.

How to Handle:

Sorting allows identifying this skew early, but the algorithm should still correctly iterate, summing until it reaches the point where consecutive sums are no longer possible.

Large input array to check for efficiency, e.g. an array containing 10000 values.

How to Handle:

The solution's time complexity should ideally be O(n log n) due to sorting, and large inputs should be handled efficiently within reasonable time limits.

Array that already allows forming 0, 1, 2, ..., k and a coin value of k+2 is added.

How to Handle:

The next consecutive number that can be made is k+1, so the result should still be k+1 even with the k+2 coin.