# Maximum Number of Integers to Choose From a Range I **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-i) Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-integers-to-choose-from-a-range-i **Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy) **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Hash Table **Companies:** [PayPal](https://scaleengineer.com/companies/paypal) --- ## Problem 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 <= 104` * `1 <= banned[i], n <= 104` * `1 <= maxSum <= 109` # Approaches ## Brute Force with Linear Scan This approach uses a greedy strategy by iterating through numbers from 1 to `n` and picking the smallest available integers first. To check if a number is banned, it performs a simple linear scan through the `banned` array. This is the most straightforward but also the least efficient method. **Time:** O(n * B), where `n` is the upper limit of the range and `B` is the length of the `banned` array. The outer loop runs up to `n` times, and for each iteration, we scan the `banned` array, which takes `O(B)` time. · **Space:** O(1), as we only use a few variables to store the state, regardless of the input size. **Pros:** Simple to understand and implement.; Very low memory usage as it doesn't require any extra data structures. **Cons:** Highly inefficient for the given constraints, with a time complexity of `O(n * B)`. This is likely to cause a 'Time Limit Exceeded' error on most coding platforms. ### Explanation The core idea is to maximize the number of chosen integers. A greedy strategy works best here: by always choosing the smallest possible integers, we leave the maximum possible budget in `maxSum` for subsequent integers. The algorithm proceeds as follows: 1. Initialize a counter `count` to 0 and a running sum `currentSum` to 0. We use a `long` for `currentSum` to avoid potential overflow since `maxSum` can be large. 2. We loop through each integer `i` from 1 to `n`. 3. For each `i`, we first check if we can afford to add it. If `currentSum + i > maxSum`, we break the loop because any number greater than `i` will also violate the condition. 4. If we can afford `i`, we then check if it's a banned number. This is done by iterating through the entire `banned` array. A flag, `isBanned`, can be used to track this. 5. If `i` is not banned, we choose it: increment `count` and add `i` to `currentSum`. 6. After the loop finishes (either by reaching `n` or by exceeding `maxSum`), we return the final `count`. ```java class Solution { public int maxCount(int[] banned, int n, int maxSum) { long currentSum = 0; int count = 0; for (int i = 1; i <= n; i++) { if (currentSum + i > maxSum) { break; } boolean isBanned = false; for (int b : banned) { if (b == i) { isBanned = true; break; } } if (!isBanned) { currentSum += i; count++; } } return count; } } ``` ### Algorithm * Initialize `count` of chosen integers to 0 and `currentSum` (as a long to prevent overflow) to 0. * Iterate with a number `i` from 1 to `n`. * For each `i`, perform a linear scan through the `banned` array to check if `i` is present. * If `i` is not in `banned` and `currentSum + i` does not exceed `maxSum`: * Increment `count`. * Add `i` to `currentSum`. * If `currentSum + i` exceeds `maxSum`, stop the process as any subsequent number will also exceed the limit. * Return the final `count`. ## Optimized Greedy Approach with a HashSet This approach also uses the same greedy strategy of picking the smallest available integers first. However, it significantly optimizes the check for banned numbers. By pre-processing the `banned` array into a `HashSet`, we can check if a number is banned in average O(1) time, making the overall solution much faster. **Time:** O(n + B), where `n` is the range limit and `B` is the length of `banned`. It takes `O(B)` to build the set and `O(n)` to iterate from 1 to `n` with constant-time lookups. · **Space:** O(B), where `B` is the number of elements in the `banned` array. This space is used to store the `HashSet` of banned numbers. **Pros:** Very efficient time complexity, making it suitable for large inputs.; Maintains the simple and intuitive greedy logic. **Cons:** Uses extra space proportional to the number of banned items, which could be a concern if memory is extremely constrained. ### Explanation The bottleneck in the brute-force approach is the repeated linear scan of the `banned` array. We can eliminate this by using a data structure that provides fast lookups. A `HashSet` is ideal for this purpose. The improved algorithm is as follows: 1. First, create a `HashSet` and populate it with all the elements from the `banned` array. This step takes `O(B)` time, where `B` is the length of `banned`. 2. Initialize `count = 0` and `currentSum = 0L`. 3. Iterate through integers `i` from 1 to `n`. 4. In each iteration, first check if `currentSum + i > maxSum`. If it is, we break the loop. 5. Next, check if `i` is in our `bannedSet`. This is now an `O(1)` average time operation. 6. If `i` is not in the `bannedSet`, we select it by incrementing `count` and adding `i` to `currentSum`. 7. Finally, return the total `count`. This optimization reduces the overall time complexity from quadratic to linear, making it efficient enough for the given constraints. ```java import java.util.HashSet; import java.util.Set; class Solution { public int maxCount(int[] banned, int n, int maxSum) { Set bannedSet = new HashSet<>(); for (int b : banned) { bannedSet.add(b); } long currentSum = 0; int count = 0; for (int i = 1; i <= n; i++) { if (!bannedSet.contains(i)) { if (currentSum + i <= maxSum) { currentSum += i; count++; } else { break; } } } return count; } } ``` ### Algorithm * Create a `HashSet` to store all the numbers from the `banned` array for efficient lookup. * Initialize `count` of chosen integers to 0 and `currentSum` (as a long) to 0. * Iterate with a number `i` from 1 to `n`. * For each `i`, check if it exists in the `banned` set in `O(1)` average time. * If `i` is not in the `banned` set and `currentSum + i` does not exceed `maxSum`: * Increment `count`. * Add `i` to `currentSum`. * If `currentSum + i` exceeds `maxSum`, stop the process. * Return the final `count`. # Solutions ### Java ```java class Solution { public int maxCount(int[] banned, int n, int maxSum) { Set ban = new HashSet<>(banned.length); for (int x : banned) { ban.add(x); } int ans = 0, s = 0; for (int i = 1; i <= n && s + i <= maxSum; ++i) { if (!ban.contains(i)) { ++ans; s += i; } } return ans; } } ``` ### CPP ```cpp class Solution { public: int maxCount(vector &banned, int n, int maxSum) { unordered_set ban(banned.begin(), banned.end()); int ans = 0, s = 0; for (int i = 1; i <= n && s + i <= maxSum; ++i) { if (!ban.count(i)) { ++ans; s += i; } } return ans; } }; ``` ### Python ```python 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 ```