#2554

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Number of Integers to Choose From a Range I

Determine the maximum count of integers from 1 to n avoiding banned numbers while keeping the sum under maxSum.

array hash table binary search greedy sorting

Problem Statement

You are given an integer array banned and two integers n and maxSum. You need to select numbers from 1 to n such that no selected number appears in banned, and the sum of selected numbers does not exceed maxSum.

Return the maximum number of integers you can pick following these rules. For example, given banned = [1,6,5], n = 5, maxSum = 6, you can choose 2 and 4, totaling 2 integers. Another example: banned = [11], n = 7, maxSum = 50 allows picking 1 through 7 for a total of 7 integers.

Examples

Example 1

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

Output: 2

You can choose the integers 2 and 4. 2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.

Example 2

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

Output: 0

You cannot choose any integer while following the mentioned conditions.

Example 3

Input: banned = [11], n = 7, maxSum = 50

Output: 7

You can choose the integers 1, 2, 3, 4, 5, 6, and 7. They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.

Constraints

1 <= banned.length <= 104
1 <= banned[i], n <= 104
1 <= maxSum <= 109

Solution Approach

Use a Hash Set for Banned Numbers

Place all banned numbers that are <= n into a hash set to allow constant-time checks. This prevents mistakenly adding banned numbers and ensures array scanning remains efficient.

Incremental Array Scanning

Scan integers from 1 to n, adding each number not in the banned set to a cumulative sum. Stop adding once adding the next number would exceed maxSum. Count each successfully added number to determine the maximum.

Greedy Selection Strategy

Always choose the smallest available number first, as picking larger numbers early risks exceeding maxSum prematurely. This greedy approach aligns with array scanning plus hash lookup patterns and maximizes the count of valid integers.

Complexity Analysis

Metric	Value
Time	O(m + n)
Space	O(m)

Time complexity is O(m + n) where m is the length of banned, due to building the hash set and scanning the range. Space complexity is O(m) for storing banned numbers in the hash set.

What Interviewers Usually Probe

Checking whether candidate numbers fall in banned set.
Evaluating cumulative sum to avoid exceeding maxSum.
Expecting a greedy selection from smallest to largest integers.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude banned numbers greater than n.
Adding numbers until maxSum is exceeded instead of stopping before.
Not using a hash set, leading to O(n*m) time complexity.

Follow-up variants

Allow negative numbers in the range and adjust sum constraints accordingly.
Select numbers with replacement to maximize the count under maxSum.
Optimize for multiple queries with different maxSum values over the same banned list.

FAQ

What is the best way to handle banned numbers in this problem?

Use a hash set to store all banned numbers less than or equal to n for constant-time lookups while scanning the array.

How does the array scanning plus hash lookup pattern apply here?

Scan numbers sequentially from 1 to n and check against the hash set to quickly skip banned numbers, maintaining efficient O(n + m) time.

Can the solution handle large maxSum values efficiently?

Yes, because it stops scanning once the cumulative sum would exceed maxSum, preventing unnecessary computation.

Should I pick larger numbers first to maximize the sum?

No, selecting the smallest numbers first is a greedy strategy to maximize the count without exceeding maxSum, which is the primary goal.

What is the main failure mode to avoid in Maximum Number of Integers to Choose From a Range I?

Failing to exclude banned numbers or exceeding maxSum early are common mistakes; using the hash set and incremental scanning prevents this.

terminal

Solution

Solution 1: Greedy + Enumeration

We use the variable $s$ to represent the sum of the currently selected integers, and the variable $ans$ to represent the number of currently selected integers. We convert the array `banned` into a hash table for easy determination of whether a certain integer is not selectable.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        ans = s = 0
        ban = set(banned)
        for i in range(1, n + 1):
            if s + i > maxSum:
                break
            if i not in ban:
                ans += 1
                s += i
        return ans

Solution 2: Greedy + Binary Search

If $n$ is very large, the enumeration in Method One will time out.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        ans = s = 0
        ban = set(banned)
        for i in range(1, n + 1):
            if s + i > maxSum:
                break
            if i not in ban:
                ans += 1
                s += i
        return ans

Continue Practicing

#2501 longest square streak in an array #2713 maximum strictly increasing cells in a matrix #2830 maximize the profit as the salesman