problemmediumalgorithmsleetcode-2557leetcode 2557leetcode2557

Maximum Number of Integers to Choose From a Range II

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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.

Examples

Example 1

Input: banned = [1,4,6], n = 6, maxSum = 4
Output: 1
Explanation: You can choose the integer 3.
3 is in the range [1, 6], and do not appear in banned. The sum of the chosen integers is 3, which does not exceed maxSum.

Example 2

Input: banned = [4,3,5,6], n = 7, maxSum = 18
Output: 3
Explanation: You can choose the integers 1, 2, and 7.
All these integers are in the range [1, 7], all do not appear in banned, and their sum is 18, which does not exceed maxSum.
[]()```

### Constraints

- `1 <= banned.length <= 10^5`
- `1 <= banned[i] <= n <= 10^9`
- `1 <= maxSum <= 10^15`

## Solution

### Method 1 – Greedy + Skipping Banned Numbers

#### Intuition

To maximize the count of chosen numbers, always pick the smallest available number not in `banned` and keep adding until the sum exceeds `maxSum`. Skipping banned numbers ensures we only consider valid picks.

#### Approach

1. Add all banned numbers to a set for O(1) lookup.
2. Initialize `ans` (count) and `curr_sum` (current sum) to 0.
3. Iterate from 1 to `n`:
  - If the number is banned, skip it.
  - If adding the number to `curr_sum` exceeds `maxSum`, stop.
  - Otherwise, add the number to `curr_sum` and increment `ans`.
4. Return `ans`.

#### Code

{{< code_tabs >}}
##### C++

```cpp
class Solution {
public:
   int maxCount(vector<int>& banned, int n, int maxSum) {
      unordered_set<int> ban(banned.begin(), banned.end());
      int ans = 0;
      long long curr_sum = 0;
      for (int i = 1; i <= n; ++i) {
        if (ban.count(i)) continue;
        if (curr_sum + i > maxSum) break;
        curr_sum += i;
        ++ans;
      }
      return ans;
   }
};
Go
func maxCount(banned []int, n int, maxSum int) int {
   ban := make(map[int]bool)
   for _, v := range banned {
      ban[v] = true
   }
   ans := 0
   currSum := 0
   for i := 1; i <= n; i++ {
      if ban[i] {
        continue
      }
      if currSum+i > maxSum {
        break
      }
      currSum += i
      ans++
   }
   return ans
}
Java
class Solution {
   public int maxCount(int[] banned, int n, int maxSum) {
      Set<Integer> ban = new HashSet<>();
      for (int b : banned) ban.add(b);
      int ans = 0;
      long currSum = 0;
      for (int i = 1; i <= n; i++) {
        if (ban.contains(i)) continue;
        if (currSum + i > maxSum) break;
        currSum += i;
        ans++;
      }
      return ans;
   }
}
Kotlin
class Solution {
   fun maxCount(banned: IntArray, n: Int, maxSum: Int): Int {
      val ban = banned.toHashSet()
      var ans = 0
      var currSum = 0L
      for (i in 1..n) {
        if (i in ban) continue
        if (currSum + i > maxSum) break
        currSum += i
        ans++
      }
      return ans
   }
}
Python
class Solution:
   def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:
      ban = set(banned)
      ans = 0
      curr_sum = 0
      for i in range(1, n + 1):
        if i in ban:
           continue
        if curr_sum + i > maxSum:
           break
        curr_sum += i
        ans += 1
      return ans
Rust
use std::collections::HashSet;
impl Solution {
   pub fn max_count(banned: Vec<i32>, n: i32, max_sum: i64) -> i32 {
      let ban: HashSet<i32> = banned.into_iter().collect();
      let mut ans = 0;
      let mut curr_sum = 0i64;
      for i in 1..=n {
        if ban.contains(&i) { continue; }
        if curr_sum + i as i64 > max_sum { break; }
        curr_sum += i as i64;
        ans += 1;
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(m + min(n, maxSum)), where m = banned.length. In practice, the loop stops early due to the sum constraint.
  • 🧺 Space complexity: O(m) for the banned set.

Comments