LeetCode 2554 - Maximum Number of Integers to Choose From a Range I

LeetCode Problem 2554

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Greedy, Sorting

Solution

Problem Understanding

The problem gives us three inputs:

• banned, an array of integers that are not allowed to be selected
• n, which defines the valid integer range [1, n]
• maxSum, the maximum total sum allowed for all chosen integers

We must choose as many distinct integers as possible while satisfying four conditions:

1. Every chosen integer must be between 1 and n
2. No integer can be chosen more than once
3. No chosen integer can appear in banned
4. The total sum of all chosen integers must be less than or equal to maxSum

The goal is not to maximize the sum, but to maximize the number of selected integers.

This distinction is very important. If we want the largest possible count, we should prefer smaller numbers because they consume less of the available sum budget. For example, choosing 1 + 2 + 3 gives three integers for a sum of 6, while choosing 6 alone gives only one integer for the same sum.

The constraints are relatively small:

• banned.length <= 10^4
• n <= 10^4
• maxSum <= 10^9

Since n is only up to 10^4, iterating through all numbers from 1 to n is completely feasible. The important part is efficiently checking whether a number is banned. A linear search through banned for every candidate would be unnecessarily slow, so we should use a hash-based structure for constant time membership checks.

Several edge cases are important:

• All numbers may be banned
• maxSum may be too small to select even the smallest valid number
• banned may contain values larger than n, which should simply be ignored
• The optimal solution may require stopping early once adding another number exceeds maxSum
• Duplicate values may appear in banned, so using a set is helpful

Approaches

Brute Force Approach

A straightforward brute-force solution would try every possible subset of integers from [1, n], filter out subsets containing banned numbers, compute their sums, and track the subset with the largest size whose sum does not exceed maxSum.

This works because it explicitly checks every possible valid selection, guaranteeing the optimal answer is found.

However, this approach is extremely inefficient. There are 2^n possible subsets, which becomes impossible even for moderate values of n. Since n can be 10^4, this method is completely impractical.

Another less extreme brute-force variant would repeatedly search the banned array linearly for each number from 1 to n. While much better than subset enumeration, this still leads to unnecessary repeated work.

Optimal Greedy Approach

The key insight is that if we want to maximize the number of selected integers, we should always choose the smallest available valid numbers first.

This is a classic greedy observation. Smaller numbers consume less of the maxSum budget, leaving room to include more integers later.

For example:

• Choosing 1 + 2 + 3 = 6 gives three numbers
• Choosing 6 gives only one number

So the optimal strategy is:

1. Iterate from 1 to n
2. Skip banned numbers
3. Add the current number if the running sum stays within maxSum
4. Stop once the next number would exceed the limit

To efficiently check whether a number is banned, we store all banned values in a hash set.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Enumerates all subsets
Optimal	O(n + b)	O(b)	Greedy selection with hash set lookup

Here, b represents the size of banned.

Algorithm Walkthrough

1. Create a hash set from the banned array.

A hash set allows constant time membership checks. This is much faster than repeatedly scanning the array. 2. Initialize two variables:

• current_sum = 0
• count = 0

current_sum tracks the total of selected integers, and count tracks how many integers we have chosen. 3. Iterate through every integer from 1 to n.

We process numbers in increasing order because smaller numbers are always more beneficial when trying to maximize count. 4. For each number:

• If it exists in the banned set, skip it.
• Otherwise, check whether adding it would exceed maxSum.

5. If current_sum + number <= maxSum:

• Add the number to the running sum
• Increment the count

6. Otherwise, stop the iteration immediately.

Since numbers are increasing, every future number will be even larger. If the current number cannot fit, no later number can fit either. 7. Return count.

Why it works

The greedy strategy is correct because choosing a smaller valid number always leaves at least as much remaining budget as choosing a larger one.

Suppose an optimal solution skipped a smaller valid number in favor of a larger one. Replacing the larger number with the smaller one would reduce or maintain the total sum while keeping the same count, and potentially allow additional numbers to fit later. Therefore, selecting numbers in ascending order always leads to the maximum possible count.

Python Solution

from typing import List

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned_set = set(banned)

        current_sum = 0
        count = 0

        for number in range(1, n + 1):
            if number in banned_set:
                continue

            if current_sum + number > maxSum:
                break

            current_sum += number
            count += 1

        return count

The implementation begins by converting banned into a set. This improves lookup performance from linear time to constant time on average.

The algorithm then iterates through all integers from 1 to n. For each number, it first checks whether the number is banned. If so, the loop skips that value immediately.

If the number is allowed, the algorithm checks whether adding it would exceed maxSum. If the sum would become too large, the loop terminates because all future numbers are larger and therefore cannot fit either.

Otherwise, the number is included in the selection, the running sum is updated, and the count increases.

Finally, the method returns the total number of chosen integers.

Go Solution

func maxCount(banned []int, n int, maxSum int) int {
    bannedSet := make(map[int]bool)

    for _, num := range banned {
        bannedSet[num] = true
    }

    currentSum := 0
    count := 0

    for number := 1; number <= n; number++ {
        if bannedSet[number] {
            continue
        }

        if currentSum+number > maxSum {
            break
        }

        currentSum += number
        count++
    }

    return count
}

The Go solution follows the same logic as the Python implementation. Since Go does not have a built in hash set type, a map[int]bool is used instead.

Integer overflow is not a concern here because the maximum possible sum is well within Go's standard integer range.

The algorithm uses a simple for loop to iterate through the range [1, n], maintaining the running sum and count exactly as in the Python version.

Worked Examples

Example 1

Input:

banned = [1,6,5]
n = 5
maxSum = 6

Banned set:

{1,5,6}

Current Number	Banned?	Current Sum Before	Can Add?	Current Sum After	Count
1	Yes	0	No	0	0
2	No	0	Yes	2	1
3	No	2	Yes	5	2
4	No	5	No	5	2

The algorithm stops at 4 because adding it would exceed maxSum.

Final answer:

2

Example 2

Input:

banned = [1,2,3,4,5,6,7]
n = 8
maxSum = 1

Banned set:

{1,2,3,4,5,6,7}

Current Number	Banned?	Current Sum Before	Can Add?	Current Sum After	Count
1	Yes	0	No	0	0
2	Yes	0	No	0	0
3	Yes	0	No	0	0
4	Yes	0	No	0	0
5	Yes	0	No	0	0
6	Yes	0	No	0	0
7	Yes	0	No	0	0
8	No	0	No	0	0

Adding 8 would exceed maxSum = 1.

Final answer:

0

Example 3

Input:

banned = [11]
n = 7
maxSum = 50

Since 11 is outside the range [1, 7], it has no effect.

Current Number	Banned?	Current Sum Before	Can Add?	Current Sum After	Count
1	No	0	Yes	1	1
2	No	1	Yes	3	2
3	No	3	Yes	6	3
4	No	6	Yes	10	4
5	No	10	Yes	15	5
6	No	15	Yes	21	6
7	No	21	Yes	28	7

Final answer:

7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + b)	Building the set takes O(b), iterating from 1 to n takes O(n)
Space	O(b)	The banned set stores all banned values

The dominant operations are constructing the hash set and scanning the range [1, n]. Each membership check in the set is constant time on average, making the overall algorithm linear with respect to the input size.

Test Cases

from typing import List

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned_set = set(banned)

        current_sum = 0
        count = 0

        for number in range(1, n + 1):
            if number in banned_set:
                continue

            if current_sum + number > maxSum:
                break

            current_sum += number
            count += 1

        return count

solution = Solution()

# Provided example 1
assert solution.maxCount([1, 6, 5], 5, 6) == 2

# Provided example 2
assert solution.maxCount([1, 2, 3, 4, 5, 6, 7], 8, 1) == 0

# Provided example 3
assert solution.maxCount([11], 7, 50) == 7

# No banned numbers
assert solution.maxCount([], 5, 10) == 4  # picks 1,2,3,4

# maxSum too small for any number
assert solution.maxCount([2, 3], 5, 0) == 0

# All numbers banned
assert solution.maxCount([1, 2, 3, 4, 5], 5, 100) == 0

# Banned values outside range
assert solution.maxCount([100, 200], 5, 10) == 4

# Duplicate banned values
assert solution.maxCount([2, 2, 2], 5, 10) == 3

# Early stopping due to sum limit
assert solution.maxCount([], 100, 3) == 2  # picks 1 and 2

# Large n with moderate sum
assert solution.maxCount([], 10000, 15) == 5  # 1+2+3+4+5=15

Test	Why
[1,6,5], n=5, maxSum=6	Validates standard mixed case
[1,2,3,4,5,6,7], n=8, maxSum=1	Validates impossible selection
[11], n=7, maxSum=50	Ensures out of range banned values are ignored
[], n=5, maxSum=10	Tests behavior with no banned numbers
maxSum=0	Ensures no selections are made when budget is too small
All numbers banned	Verifies complete exclusion handling
Banned values outside range	Confirms irrelevant banned values do not affect result
Duplicate banned values	Ensures set conversion handles duplicates correctly
Early stopping case	Verifies break condition works
Large n with small sum	Confirms greedy selection behavior

Edge Cases

One important edge case occurs when every number in the range is banned. A careless implementation might still attempt to add numbers or fail to handle an empty valid set correctly. This implementation safely skips all banned values and returns 0 when no valid numbers can be selected.

Another important case happens when maxSum is extremely small. For example, if maxSum = 1 and the number 1 is banned, then no valid selection exists. The algorithm correctly checks the sum before adding each number and returns 0 immediately when nothing fits.

A third edge case involves banned values that lie outside the valid range [1, n]. These values should have no effect because they could never be selected anyway. Since the algorithm only iterates from 1 to n, out of range banned numbers are naturally ignored without requiring any special handling.

Duplicate entries in banned are also worth considering. If the banned array contains repeated values, using a list lookup could lead to redundant work. Converting the array into a set automatically removes duplicates and guarantees efficient membership checks.

Finally, early termination is important for efficiency and correctness. Once the current number cannot fit within the remaining budget, every later number will also fail because the sequence is increasing. The implementation uses break at this point, avoiding unnecessary iterations.