Start by scanning numbers from 1 to n and keep banned integers in a hash set for quick lookup. Incrementally add numbers not in the banned set, stopping when the cumulative sum would exceed maxSum. This approach efficiently maximizes the chosen integers using array scanning plus hash lookup, while handling edge cases where early numbers may already breach the sum limit.
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.
How GhostInterview Helps
- Highlights the array scanning plus hash lookup pattern to quickly identify valid numbers.
- Shows step-by-step sum accumulation with early stopping when maxSum is reached.
- Illustrates greedy selection to maximize count while handling edge cases efficiently.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Maximum Number of Integers to Choose From a Range I instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Maximum Number of Integers to Choose From a Range I from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the length of the longest subsequence where each element is a perfect square of its previous one.
Open problem page#2713 Maximum Strictly Increasing Cells in a MatrixFind the maximum number of cells that can be visited in a matrix by following strictly increasing values from a starting cell.
Open problem page#2830 Maximize the Profit as the SalesmanDetermine the maximum profit a salesman can earn by strategically selecting non-overlapping offers on consecutive houses.
Open problem page