Maximum Number of Consecutive Values You Can Make - Video Solutions

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.