1798. Maximum Number of Consecutive Values You Can Make

Problem Description

The problem presents us with an array coins, each element representing the value of a coin that we have in our possession. The goal is to determine the maximum number of consecutive integer values that we can create by combining these coins, starting from and including the value 0. It is also mentioned that it's possible to have multiple coins of the same value.

The task can be visualized as a game where we are trying to create a continuous sequence of values starting from zero by selecting coins from the array. The challenge is to find out how long this sequence can be before we encounter a gap that cannot be filled with the available coins.

Intuition

The solution to the problem lies in sorting the array and then iteratively adding the value of coins to a running sum, maintaining the maximum consecutive sequence that can be produced.

We start with an answer ans initialized to 1, which represents the smallest sum we aim to create. Intuitively, if we include value 0 which doesn’t require any coins, we can surely create at least 1 as the next consecutive integer value using our coins.

The sorted array allows us to approach the problem in an incremental manner. We iterate through each coin, and for each coin, we check if its value is greater than the current sum ans.

If the coin's value is less than or equal to ans, we can add this coin to the previous sum to extend our consecutive sequence up to the new sum.
If the coin's value is more than ans, this indicates that there's a gap we cannot fill using our coins as all smaller coins have already been processed. So, we break the loop.

After processing each coin or upon encountering a gap, the current value of ans represents the maximum number of consecutive integer values attainable.

The reason this approach works is that once coins are sorted, combining them from the smallest to the largest ensures that we are filling in the smallest possible gaps first, thus extending the consecutive sequence without missing any possible value.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a greedy approach using simple control structures and a sorting algorithm.

First, we sort the array. This is essential for the greedy algorithm to work because we want to consider coins in ascending order to build up the consecutive sequence without any gaps.

for v in sorted(coins):

Once the coins are sorted, we use a for-loop to iterate through each coin. The variable ans is initialized to 1, which acts as both the accumulator and the tracker for the consecutive numbers that can be made with the coins seen so far.

ans = 1

We iterate through each coin's value in the sorted list. For each value v, we check if v is larger than ans. If it is not, we add the value of v to ans. This addition is the act of creating a new consecutive number by adding the value of the coin to the sum of values that we could already create.

if v > ans:
    break
ans += v

The above conditional is used to check for the presence of a gap. If the value of the current coin is greater than the current ans value, there is a break in our consecutive numbers, and we cannot extend our sequence further with the current coin. In this case, we break out of the loop and return the maximum consecutive number that we can make until now (since further numbers cannot be made consecutively with what we have).

The break statement ends the loop when a gap is found. If all coins are processed without encountering a gap, the loop concludes naturally.

Finally, we return ans, which now indicates the maximum sum we could reach consecutively with the given coins.

return ans

This algorithm is efficient because the costly operation is the initial sorting which typically has a time complexity of O(n log n), where n is the number of coins. The subsequent iteration is an O(n) operation, making the total complexity O(n log n). The space complexity is O(1) since we are not using any additional data structures proportional to the input size.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's apply the solution approach to a small set of coins to see how it works. Suppose we have the following coins: coins = [1,2,3,4]. Our task is to determine the maximum number of consecutive integer values we can create starting from 0. Let's walk through the steps specified in the solution approach:

First, we sort the coins, but since they are already in ascending order (1, 2, 3, 4), we don't need to do anything.
We initialize ans to 1. This represents the smallest sum we aim to create, understanding that a sum of 0 can always be created without using any coins.
We iterate through each coin in the array. The sorted array is coins = [1,2,3,4].
- For the first coin (v = 1), since v <= ans (1 <= 1), we add v to ans. Now, ans = ans + v = 2. We can now create all sums up to and including 2.
- The next coin is v = 2. Since v <= ans (2 <= 2), we can add v to ans, making ans = 4. Now we can create all sums up to and including 4.
- We move to the next coin (v = 3). Again, v <= ans (3 <= 4), so we add v to ans, which becomes ans = 7. We can create all sums up to and including 7.
- Lastly, we have the coin v = 4. It is also less than or equal to ans (4 <= 7), so we add v to ans to get ans = 11. We can create sums up to and including 11.
- Since we did not encounter any coin v such that v > ans throughout the entire iteration, we do not hit the break statement in our loop.
After processing all the coins, the current value of ans is 11, which means we can create every consecutive integer value from 0 to 11 with the given coins.
We return ans which is 11 in this case, indicating the maximum number we can reach consecutively.

In conclusion, with the given array of coins = [1,2,3,4], we can create all consecutive integer values from 0 up to 11. The greedy algorithm efficiently allows us to determine this by adding coins in ascending order and checking for any possible gaps.

Solution Implementation

1class Solution:
2    def getMaximumConsecutive(self, coins: List[int]) -> int:
3        # The variable `max_consecutive` is used to track the highest consecutive
4        # amount that can be obtained with the current set of coins.
5        max_consecutive = 1
6      
7        # Loop through the coins sorted in ascending order
8        for coin in sorted(coins):
9            # If the current coin value is greater than the highest consecutive
10            # amount that can be formed, we cannot create the next consecutive
11            # number, so we break the loop.
12            if coin > max_consecutive:
13                break
14          
15            # Otherwise, we add the value of the current coin to the highest
16            # consecutive amount to increase the range of consecutive amounts
17            # that can be formed.
18            max_consecutive += coin
19      
20        # After processing all the coins we can, return the highest consecutive
21        # amount that we were able to reach.
22        return max_consecutive
23

1import java.util.Arrays; // Import Arrays utility for sorting
2
3class Solution {
4    // Method to find the maximum consecutive integer that cannot be created using a given set of coins
5    public int getMaximumConsecutive(int[] coins) {
6        // Sort the coins array to consider coins in increasing order
7        Arrays.sort(coins);
8
9        // Initialize the answer to 1, since we start checking from the first positive integer
10        int maxConsecutive = 1;
11
12        // Iterate through the sorted coins
13        for (int coin : coins) {
14            // If the current coin's value is greater than the current maximum consecutive integer,
15            // we cannot extend the consecutive sequence any further
16            if (coin > maxConsecutive) {
17                break;
18            }
19            // Otherwise, increase the maximum consecutive integer by the value of the current coin
20            // This is because we can create all values from 1 to current maxConsecutive with the coins seen so far
21            // and adding the current coin allows us to extend this sequence further
22            maxConsecutive += coin;
23        }
24
25        // Return the maximum consecutive integer that cannot be formed
26        return maxConsecutive;
27    }
28}
29

1#include <vector>   // Include necessary header for vector
2#include <algorithm> // Include necessary header for sort function
3
4class Solution {
5public:
6    // Function to find the maximum consecutive value that cannot be obtained with a given set of coins
7    int getMaximumConsecutive(std::vector<int>& coins) {
8        // Sort the coins in non-decreasing order
9        std::sort(coins.begin(), coins.end());
10
11        // Initialize the answer to 1 (the smallest positive integer)
12        int maxConsecutive = 1;
13
14        // Iterate through the sorted vector of coins
15        for (int coin : coins) {
16            // If the current coin value is greater than the current possible consecutive value, break the loop
17            if (coin > maxConsecutive) break;
18
19            // Otherwise, add the value of the coin to the maxConsecutive to extend the range of possible consecutive values
20            maxConsecutive += coin;
21        }
22
23        // Return the first maximum consecutive value that cannot be obtained
24        return maxConsecutive;
25    }
26};
27

1// Import necessary functionalities
2import { sort } from 'algorithm'; // TypeScript does not have these, assuming they exist.
3
4// Declare the function to find the maximum consecutive value that cannot be obtained with a given set of coins
5function getMaximumConsecutive(coins: number[]): number {
6    // Sort the coins in non-decreasing order
7    coins.sort((a, b) => a - b);
8
9    // Initialize the answer to 1(the smallest positive integer)
10    let maxConsecutive = 1;
11
12    // Iterate through the sorted array of coins
13    for (let coin of coins) {
14        // If the current coin value is greater than the current possible consecutive value, break the loop
15        if (coin > maxConsecutive) break;
16
17        // Otherwise, add the value of the coin to maxConsecutive to extend the range of possible consecutive values
18        maxConsecutive += coin;
19    }
20
21    // Return the first maximum consecutive value that cannot be obtained
22    return maxConsecutive;
23}
24

Time and Space Complexity

Time Complexity

The provided code snippet has a time complexity of O(n log n) due to the sorting operation, where n is the number of elements in the coins list. The sorted function in Python uses the Timsort algorithm, which has this time complexity on average and in the worst case. Following the sorting, the code iterates through the sorted coins once, which has a time complexity of O(n). However, since sorting is the dominant operation, the overall time complexity of the code remains O(n log n).

Space Complexity

The space complexity of the code is O(n). This is because the sorted function returns a new list containing the sorted elements, therefore it requires additional space proportional to the size of the input list. The other variables used in the function (ans and v) use constant space and do not depend on the size of the input, so they do not affect the overall space complexity.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know