Watch 10 video solutions for Maximum Number of Integers to Choose From a Range I, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by codestorywithMIK has 5,061 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:
[1, n].banned.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 <= 109Problem 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 | 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. |