Is Maximum Number of Consecutive Values You Can Make easy or hard?

Maximum Number of Consecutive Values You Can Make is rated Medium on LeetCode with an acceptance rate around 60%. The implementation is short, but identifying the greedy invariant `reach + 1` that determines when the sequence breaks is the main challenge.

How to solve Maximum Number of Consecutive Values You Can Make in O(n)?

A pure O(n) approach is generally not possible because the coin values must be processed in sorted order to apply the greedy rule. The typical solution sorts the array first and then iterates once while maintaining the current reachable range. The resulting complexity is O(n log n) time and O(1) space.

Maximum Number of Consecutive Values You Can Make Python or Java solution?

Implement the greedy approach by sorting the array and maintaining a variable `reach`. Iterate through the coins and stop when a coin exceeds `reach + 1`; otherwise extend `reach` by that coin value. This implementation works identically in Python, Java, C++, JavaScript, and C#.

What is the best approach for Maximum Number of Consecutive Values You Can Make?

The best approach is a greedy strategy combined with sorting. After sorting the coins, track the maximum reachable value `reach`. If the next coin value is less than or equal to `reach + 1`, extend the reachable range by adding the coin. Otherwise a gap appears and the sequence stops. This method runs in O(n log n) time due to sorting and uses O(1) extra space.

What data structure is used in Maximum Number of Consecutive Values You Can Make?

The optimal solution primarily uses a sorted array and a running integer variable to track the reachable range. No complex data structures are required. A brute-force alternative may use a hash set or DP array to track achievable subset sums.

What is the time complexity of Maximum Number of Consecutive Values You Can Make?

The optimal greedy solution runs in O(n log n) time because the coins must be sorted first. After sorting, a single linear scan processes each coin once, which takes O(n). The space complexity is O(1) if sorting is done in place.

Is Maximum Number of Consecutive Values You Can Make asked at Google, Amazon, or Meta?

Greedy range-expansion problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. The problem tests whether candidates can identify a greedy invariant (`reachable range`) rather than relying on heavier dynamic programming.

Description Hints 3 Solution Video 11:56

1798. Maximum Number of Consecutive Values You Can Make

Medium64.4% acceptance1 company

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⁴

Asked at 1 company

Infosys

Topics

Hints open one at a time

Hint 1

If you can make the first x values and you have a value v, then you can make all the values ≤ v + x

Hint 2

Sort the array of coins. You can always make the value 0 so you can start with x = 0.

Hint 3

Process the values starting from the smallest and stop when there is a value that cannot be achieved with the current x.

11:56

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution