1798. Maximum Number of Consecutive Values You Can Make - Solution

The problem

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⁴

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.

Python

def getMaximumConsecutive(coins):
    coins.sort()
    sum_val = 0
    for coin in coins:
        if coin > sum_val + 1:
            break
        sum_val += coin
    return sum_val + 1

print(getMaximumConsecutive([1, 3]))

Java

import java.util.Arrays;

public class Solution {
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int sum = 0;
        for (int coin : coins) {
            if (coin > sum + 1) break;
            sum += coin;
        }
        return sum + 1;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] coins = {1, 3};
        System.out.println(sol.getMaximumConsecutive(coins));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int getMaximumConsecutive(std::vector<int>& coins) {
    std::sort(coins.begin(), coins.end());
    int sum = 0;
    for (int coin : coins) {
        if (coin > sum + 1) break;
        sum += coin;
    }
    return sum + 1;
}

int main() {
    std::vector<int> coins = {1, 3};
    std::cout << getMaximumConsecutive(coins) << std::endl;
    return 0;
}

JavaScript

function getMaximumConsecutive(coins) {
    coins.sort((a, b) => a - b);
    let sum = 0;
    for (let coin of coins) {
        if (coin > sum + 1) break;
        sum += coin;
    }
    return sum + 1;
}

console.log(getMaximumConsecutive([1, 3]));

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int getMaximumConsecutive(int* coins, int n) {
    qsort(coins, n, sizeof(int), compare);
    int total = 0;
    for(int i = 0; i < n; i++) {
        if (coins[i] > total + 1) break;
        total += coins[i];
    }
    return total + 1;
}

int main() {
    int coins[] = {1, 3};
    int n = sizeof(coins) / sizeof(coins[0]);
    printf("%d\n", getMaximumConsecutive(coins, n));
    return 0;
}

using System;

public class Solution {
    public int GetMaximumConsecutive(int[] coins) {
        Array.Sort(coins);
        int sum = 0;
        foreach (int coin in coins) {
            if (coin > sum + 1) break;
            sum += coin;
        }
        return sum + 1;
    }

    public static void Main() {
        Solution sol = new Solution();
        int[] coins = {1, 3};
        Console.WriteLine(sol.GetMaximumConsecutive(coins));
    }
}

The Python solution sorts the input list and initializes a sum_val variable. As it iterates through the sorted coins, it adds each coin to the sum so long as that coin does not create a gap. Once a gap is encountered, it breaks the loop and returns the sum_val + 1.

Complexity

Time Complexity: O(n log n), results from sorting the list.

Space Complexity: O(1), in-place operations are performed.

Try this approach in the editor

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.

TypeScript

function getMaximumConsecutive(coins: number[]): number {
    coins.sort((a, b) => a - b);
    let ans = 1;
    for (const v of coins) {
        if (v > ans) {
            break;
        }
        ans += v;
    }
    return ans;
}

func getMaximumConsecutive(coins []int) int {
	sort.Ints(coins)
	ans := 1
	for _, v := range coins {
		if v > ans {
			break
		}
		ans += v
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach Using Sorting	Time Complexity: O(n log n), results from sorting the list. Space Complexity: O(1), in-place operations are performed.
Sorting + Greedy	–

Approach

Complexity

Greedy Approach Using Sorting

Time Complexity: O(n log n), results from sorting the list.

Space Complexity: O(1), in-place operations are performed.

Sorting + Greedy

–

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

Frequently asked questions

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.

Maximum Number of Consecutive Values You Can Make solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Sorting

Approach 2: Sorting + Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Number of Consecutive Values You Can Make solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Sorting

Approach 2: Sorting + Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems