Maximum Number of Consecutive Values You Can Make - Solution & Explanation
Problem Statement
You are given an integer array coins of length n which represents the n coins that you own. The value of the ith 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 == n1 <= n <= 4 * 1041 <= coins[i] <= 4 * 104
Approach Overview
Problem Overview: You are given an array of coin values. Using any subset of these coins, determine the maximum number of consecutive integer values starting from 0 that can be constructed. The task is to find the largest count of consecutive values you can guarantee without gaps.
Approach 1: Subset Sum with Set/DP (Brute Force) (Time: O(n * sum), Space: O(sum))
The straightforward idea is to compute every value that can be formed using subsets of the coins. Maintain a set or boolean DP array where each position represents whether a value is achievable. For every coin, iterate over the current reachable sums and add new sums by including that coin. After processing all coins, scan from 0 upward until you hit the first value that cannot be formed. The count of values before that gap is the answer. This method clearly models the subset sum process but becomes expensive when coin values are large because the state space grows with the total sum.
Approach 2: Greedy Using Sorting (Optimal) (Time: O(n log n), Space: O(1))
The key observation is that if you can currently form every value in the range [0, reach], and the next coin value is c, then you can extend the reachable range to [0, reach + c] only if c ≤ reach + 1. If the next coin is larger than reach + 1, a gap appears and the sequence of consecutive values stops.
Start by sorting the coins using a standard sorting step. Maintain a variable reach that represents the maximum value you can currently construct. Iterate through the sorted coins. If the current coin is greater than reach + 1, you cannot build the next consecutive value, so the process stops. Otherwise, add the coin value to reach to extend the reachable range.
This greedy rule works because smaller coins expand the reachable interval gradually without leaving gaps. Sorting ensures coins are processed from smallest to largest, which guarantees that any extendable range is used immediately. The logic relies heavily on properties of cumulative sums in a sorted array and the greedy decision of always extending the smallest reachable boundary.
Recommended for interviews: Interviewers expect the greedy sorting approach. The brute-force subset method demonstrates understanding of subset sums, but the greedy observation shows strong problem-solving skills. Recognizing the reach + 1 boundary condition and combining greedy reasoning with sorting is the intended insight.
Approach 1: Greedy Approach Using Sorting
The idea is to sort the coins array and attempt to create sums starting from 0. Every time we encounter a coin whose value is greater than the current sum plus one, it indicates that we can't create the next consecutive number. By always adding the smallest coin that helps extend the sequence, we can maximize the range of numbers created.
The C solution sorts the input array first. It then initializes a total sum of 0. It iterates through the sorted coins array and continuously adds any coin to the total sum that doesn't create a gap in the range of sums possible. If a coin's value is larger than our current consecutive sum + 1, we break the loop because we cannot create the next number. Finally, the function returns the value of total + 1.
Complexity
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), not counting the input array since we do in-place operations.
Approach 2: 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.
We traverse the array, for the current element v, if v > ans, it means that we cannot construct ans+1 consecutive integers, so we directly break the loop and return ans. Otherwise, it means that we can construct ans+v consecutive integers, so we update ans to ans+v.
Finally, we return ans.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Sorting | Time Complexity: O(n log n), due to the sorting step. Space Complexity: O(1), not counting the input array since we do in-place operations. |
| Sorting + Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Subset Sum with Set/DP | O(n * sum) | O(sum) | Useful for understanding the full set of achievable sums or when practicing subset-sum style DP problems |
| Greedy After Sorting | O(n log n) | O(1) | Optimal approach for interviews and large inputs where you only need the longest consecutive constructible range |
Video Solution
Leetcode 5712. Maximum Number of Consecutive Values You Can Make • Fraz • 3,311 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Number of Consecutive Values You Can Make easy or hard?
How to solve Maximum Number of Consecutive Values You Can Make in O(n)?
Maximum Number of Consecutive Values You Can Make Python or Java solution?
What is the best approach for Maximum Number of Consecutive Values You Can Make?
What data structure is used in Maximum Number of Consecutive Values You Can Make?
What is the time complexity of Maximum Number of Consecutive Values You Can Make?
Is Maximum Number of Consecutive Values You Can Make asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Maximum Number of Consecutive Values You Can Make with our built-in code editor and test cases.
Practice on FleetCode