Maximum Number of Integers to Choose From a Range I - Solution & Explanation
Problem Statement
You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:
- The chosen integers have to be in the range
[1, n]. - Each integer can be chosen at most once.
- The chosen integers should not be in the array
banned. - The sum of the chosen integers should not exceed
maxSum.
Return the maximum number of integers you can choose following the mentioned rules.
Example 1:
Input: banned = [1,6,5], n = 5, maxSum = 6 Output: 2 Explanation: 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 Explanation: You cannot choose any integer while following the mentioned conditions.
Example 3:
Input: banned = [11], n = 7, maxSum = 50 Output: 7 Explanation: 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 <= 1041 <= banned[i], n <= 1041 <= maxSum <= 109
Approach Overview
Problem Overview: You need to pick as many integers as possible from the range [1, n]. Some numbers are banned and cannot be chosen. The total sum of the selected numbers must not exceed maxSum. The goal is to maximize how many integers you pick.
Approach 1: Greedy with Sorting (Time: O(b log b + n), Space: O(b))
This approach treats the problem as a classic greedy selection task: always pick the smallest valid number first because it consumes the least sum budget and leaves room to include more numbers later. Start by sorting the banned array using sorting. Iterate from 1 to n, skipping values that appear in the sorted banned list. For each allowed number, check if adding it keeps the running sum ≤ maxSum. If it does, include it and increase the count; otherwise stop early since larger numbers will only increase the sum further. Sorting makes it efficient to skip banned numbers with a pointer or binary search, avoiding repeated lookups.
Approach 2: Greedy without Sorting (Hash Set) (Time: O(n + b), Space: O(b))
A more direct method stores all banned values in a hash table for O(1) membership checks. Iterate sequentially from 1 to n. For each integer, perform a hash lookup to see if it is banned. If it is not banned, try adding it to the running sum. When the sum would exceed maxSum, stop the loop because future numbers are larger and will also break the constraint. This greedy ordering works because selecting smaller integers always maximizes the count of numbers under a fixed sum budget. The algorithm performs a single linear scan with constant-time checks.
Both approaches rely on the same key insight: maximizing the count under a sum constraint means prioritizing the smallest available integers. Any strategy that selects larger numbers earlier reduces the number of values you can include. Because the candidate numbers are already ordered from 1 upward, the greedy decision becomes straightforward.
Recommended for interviews: The hash-set greedy solution is typically expected. It runs in O(n + b) time and avoids sorting overhead. Explaining the greedy reasoning—"choose the smallest valid numbers first to maximize count"—demonstrates strong problem-solving clarity. Mentioning the sorted alternative shows awareness of different trade-offs when banned values must be processed efficiently.
Approach 1: Greedy Approach with Sorting
This approach involves sorting all the numbers in the range [1, n] that are not present in the banned list and iteratively selecting the smallest numbers until the sum exceeds maxSum. This strategy ensures that the maximum number of integers can be chosen because smaller numbers contribute less to the sum, allowing more numbers to be selected.
The solution defines a helper function isBanned to check if a number is banned. It then creates a list of valid numbers, sorts them, and iteratively adds them to the current sum until maxSum is exceeded.
Complexity
Time Complexity: O(n log n) due to sorting of numbers.
Space Complexity: O(n) for storing valid numbers.
Approach 2: Greedy Approach without Sorting
Instead of sorting, this approach uses a boolean array to mark banned numbers and iterates through possible selections directly in a greedy manner, quickly skipping banned numbers and tracking the sum in real-time.
This C implementation uses a boolean array to keep track of banned numbers, allowing O(1) lookups while iterating directly through the range [1, n] to accumulate the sum and count.
Complexity
Time Complexity: O(n).
Space Complexity: O(1) because the boolean array size is constant.
Approach 3: 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.
Next, we start enumerating the integer i from 1. If s + i leq maxSum and i is not in banned, then we can select the integer i, and add i and 1 to s and ans respectively.
Finally, we return ans.
The time complexity is O(n), and the space complexity is O(n). Where n is the given integer.
Approach 4: Greedy + Binary Search
If n is very large, the enumeration in Method One will time out.
We can add 0 and n + 1 to the array banned, deduplicate the array banned, remove elements greater than n+1, and then sort it.
Next, we enumerate every two adjacent elements i and j in the array banned. The range of selectable integers is [i + 1, j - 1]. We use binary search to enumerate the number of elements we can select in this range, find the maximum number of selectable elements, and then add it to ans. At the same time, we subtract the sum of these elements from maxSum. If maxSum is less than 0, we break the loop. Return the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array banned.
Similar problems:
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting of numbers. |
| Greedy Approach without Sorting | Time Complexity: O(n). |
| Greedy + Enumeration | — |
| Greedy + Binary Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(b log b + n) | O(b) | Useful when banned numbers must be processed in order or when using binary search on the banned list. |
| Greedy with Hash Set (No Sorting) | O(n + b) | O(b) | Best general solution. Fast membership checks and a single pass through the range. |
Video Solution
Maximum Number of Integers to Choose From a Range I | Simple | Leetcode 2554 | codestorywithMIK • codestorywithMIK • 5,345 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Number of Integers to Choose From a Range I easy or hard?
Maximum Number of Integers to Choose From a Range I Python/Java solution
How to solve Maximum Number of Integers to Choose From a Range I in O(n)?
What is the best approach for Maximum Number of Integers to Choose From a Range I?
Is Maximum Number of Integers to Choose From a Range I asked at Google/Amazon/Meta?
What data structure is used in Maximum Number of Integers to Choose From a Range I?
What is the time complexity of Maximum Number of Integers to Choose From a Range I?
Ready to solve this problem?
Practice Maximum Number of Integers to Choose From a Range I with our built-in code editor and test cases.
Practice on FleetCode