Maximum Number of Integers to Choose From a Range I solution and explanation
9 more videos on this problem
Maximum Number of Integers to Choose From a Range I | Simple | Leetcode 2554 | codestorywithMIKcodestorywithMIK · 11:46 · 5K views
Maximum Number of Integers to Choose From a Range I | Leetcode 2554Techdose · 6:57 · 2K views
2554. Maximum Number of Integers to Choose From a Range I (Leetcode Medium)Programming Live with Larry · 5:58 · 367 views
Leetcode 2554. Maximum Number of Integers to Choose From a Range IAlgorithms Casts · 4:19 · 348 views
Leetcode 2554 Maximum Number of Integers to Choose From a Range I (Java) - Biweekly Contest 97TheAnalyticGuy · 3:08 · 287 views
LeetCode 2554 Maximum Number of Integers to Choose From a Range I | Greedy | PayPal Interview QuesCode Harmony · 11:18 · 184 views
2554. Maximum Number of Integers to Choose From a Range I | BiWeekly Contest 97 | Unordered Map SolnTech Courses · 5:20 · 166 views
LeetCode 2554 - Maximum Number of Integers to Choose From a Range I: A Microsoft JourneyThe Lofi Dev · 5:28 · 56 views
Maximum Number of Integers to Choose From a Range I - Leetcode 2554 - JavaCode With K5KC · 6:38 · 45 views
2554. Maximum Number of Integers to Choose From a Range I | C++| Simple explanation | Leetcode| DSAAnshul Explains · 5:43 · 42 views
The 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 <= 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.
def max_numbers(banned, n, max_sum):
banned_set = set(banned)
valid_numbers = [i for i in range(1, n + 1) if i not in banned_set]
valid_numbers.sort()
current_sum = 0
chosen_count = 0
for num in valid_numbers:
if current_sum + num <= max_sum:
current_sum += num
chosen_count += 1
else:
break
return chosen_count
banned = [1, 6, 5]
n = 5
max_sum = 6
print("Maximum numbers to choose:", max_numbers(banned, n, max_sum))import java.util.*;
public class MaximumNumbers {
public static int maxNumbers(int[] banned, int n, int maxSum) {
Set<Integer> bannedSet = new HashSet<>();
for (int num : banned) bannedSet.add(num);
List<Integer> validNumbers = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!bannedSet.contains(i)) validNumbers.add(i);
}
Collections.sort(validNumbers);
int currentSum = 0;
int chosenCount = 0;
for (int num : validNumbers) {
if (currentSum + num <= maxSum) {
currentSum += num;
chosenCount++;
} else {
break;
}
}
return chosenCount;
}
public static void main(String[] args) {
int[] banned = {1, 6, 5};
int n = 5;
int maxSum = 6;
System.out.println("Maximum numbers to choose: " + maxNumbers(banned, n, maxSum));
}
}#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
int maxNumbers(const std::vector<int>& banned, int n, int maxSum) {
std::set<int> bannedSet(banned.begin(), banned.end());
std::vector<int> validNumbers;
for (int i = 1; i <= n; ++i) {
if (bannedSet.find(i) == bannedSet.end()) {
validNumbers.push_back(i);
}
}
std::sort(validNumbers.begin(), validNumbers.end());
int currentSum = 0;
int chosenCount = 0;
for (int num : validNumbers) {
if (currentSum + num <= maxSum) {
currentSum += num;
chosenCount++;
} else {
break;
}
}
return chosenCount;
}
int main() {
std::vector<int> banned = {1, 6, 5};
int n = 5;
int maxSum = 6;
std::cout << "Maximum numbers to choose: " << maxNumbers(banned, n, maxSum) << std::endl;
return 0;
}function maxNumbers(banned, n, maxSum) {
let bannedSet = new Set(banned);
let validNumbers = [];
for (let i = 1; i <= n; i++) {
if (!bannedSet.has(i)) {
validNumbers.push(i);
}
}
validNumbers.sort((a, b) => a - b);
let currentSum = 0;
let chosenCount = 0;
for (let num of validNumbers) {
if (currentSum + num <= maxSum) {
currentSum += num;
chosenCount++;
} else {
break;
}
}
return chosenCount;
}
const banned = [1, 6, 5];
const n = 5;
const maxSum = 6;
console.log("Maximum numbers to choose:", maxNumbers(banned, n, maxSum));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
bool isBanned(int *banned, int bannedSize, int num) {
for (int i = 0; i < bannedSize; ++i) {
if (banned[i] == num) return true;
}
return false;
}
int maxNumbers(int *banned, int bannedSize, int n, int maxSum) {
int *validNumbers = (int *)malloc(n * sizeof(int));
int validCount = 0;
for (int i = 1; i <= n; ++i) {
if (!isBanned(banned, bannedSize, i)) {
validNumbers[validCount++] = i;
}
}
qsort(validNumbers, validCount, sizeof(int), compare);
int currentSum = 0;
int chosenCount = 0;
for (int i = 0; i < validCount; ++i) {
if (currentSum + validNumbers[i] <= maxSum) {
currentSum += validNumbers[i];
chosenCount++;
} else {
break;
}
}
free(validNumbers);
return chosenCount;
}
int main() {
int banned[] = {1, 6, 5};
int n = 5;
int maxSum = 6;
int result = maxNumbers(banned, 3, n, maxSum);
printf("Maximum numbers to choose: %d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static int MaxNumbers(int[] banned, int n, int maxSum) {
HashSet<int> bannedSet = new HashSet<int>(banned);
List<int> validNumbers = new List<int>();
for (int i = 1; i <= n; i++) {
if (!bannedSet.Contains(i)) {
validNumbers.Add(i);
}
}
validNumbers.Sort();
int currentSum = 0, chosenCount = 0;
foreach (var num in validNumbers) {
if (currentSum + num <= maxSum) {
currentSum += num;
chosenCount++;
} else {
break;
}
}
return chosenCount;
}
static void Main() {
int[] banned = {1, 6, 5};
int n = 5;
int maxSum = 6;
Console.WriteLine("Maximum numbers to choose: " + MaxNumbers(banned, n, maxSum));
}
}This Python solution uses a set to track banned numbers, and a list comprehension to filter and sort valid numbers, then accumulates their sum until it reaches maxSum.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(n).
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.
def max_numbers(banned, n, max_sum):
banned_set = set(banned)
current_sum = 0
chosen_count = 0
for i in range(1, n + 1):
if i not in banned_set and current_sum + i <= max_sum:
current_sum += i
chosen_count += 1
return chosen_count
banned = [1, 6, 5]
n = 5
max_sum = 6
print("Maximum numbers to choose:", max_numbers(banned, n, max_sum))import java.util.*;
public class MaximumNumbersWithoutSort {
public static int maxNumbers(int[] banned, int n, int maxSum) {
Set<Integer> bannedSet = new HashSet<>();
for (int num : banned) bannedSet.add(num);
int currentSum = 0;
int chosenCount = 0;
for (int i = 1; i <= n; i++) {
if (!bannedSet.contains(i) && currentSum + i <= maxSum) {
currentSum += i;
chosenCount++;
}
}
return chosenCount;
}
public static void main(String[] args) {
int[] banned = {1, 6, 5};
int n = 5;
int maxSum = 6;
System.out.println("Maximum numbers to choose: " + maxNumbers(banned, n, maxSum));
}
}#include <iostream>
#include <unordered_set>
int maxNumbers(const int* banned, int bannedSize, int n, int maxSum) {
std::unordered_set<int> bannedSet(banned, banned + bannedSize);
int currentSum = 0;
int chosenCount = 0;
for (int i = 1; i <= n; ++i) {
if (bannedSet.find(i) == bannedSet.end() && currentSum + i <= maxSum) {
currentSum += i;
chosenCount++;
}
}
return chosenCount;
}
int main() {
int banned[] = {1, 6, 5};
int n = 5;
int maxSum = 6;
std::cout << "Maximum numbers to choose: " << maxNumbers(banned, 3, n, maxSum) << std::endl;
return 0;
}function maxNumbers(banned, n, maxSum) {
const bannedSet = new Set(banned);
let currentSum = 0;
let chosenCount = 0;
for (let i = 1; i <= n; i++) {
if (!bannedSet.has(i) && currentSum + i <= maxSum) {
currentSum += i;
chosenCount++;
}
}
return chosenCount;
}
const banned = [1, 6, 5];
const n = 5;
const maxSum = 6;
console.log("Maximum numbers to choose:", maxNumbers(banned, n, maxSum));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int maxNumbers(int *banned, int bannedSize, int n, int maxSum) {
bool bannedFlags[10001] = {0};
for (int i = 0; i < bannedSize; ++i) {
bannedFlags[banned[i]] = true;
}
int currentSum = 0;
int chosenCount = 0;
for (int i = 1; i <= n; ++i) {
if (!bannedFlags[i] && currentSum + i <= maxSum) {
currentSum += i;
chosenCount++;
}
}
return chosenCount;
}
int main() {
int banned[] = {1, 6, 5};
int n = 5;
int maxSum = 6;
int result = maxNumbers(banned, 3, n, maxSum);
printf("Maximum numbers to choose: %d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static int MaxNumbers(int[] banned, int n, int maxSum) {
HashSet<int> bannedSet = new HashSet<int>(banned);
int currentSum = 0;
int chosenCount = 0;
for (int i = 1; i <= n; i++) {
if (!bannedSet.Contains(i) && currentSum + i <= maxSum) {
currentSum += i;
chosenCount++;
}
}
return chosenCount;
}
static void Main() {
int[] banned = {1, 6, 5};
int n = 5;
int maxSum = 6;
Console.WriteLine("Maximum numbers to choose: " + MaxNumbers(banned, n, maxSum));
}
}The Python implementation directly iterates over each number, checking for its presence in a set and updating the sum if allowable, for an efficient pass through the number range.
Time Complexity: O(n).
Space Complexity: O(len(banned)).
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.
function maxCount(banned: number[], n: number, maxSum: number): number {
const set = new Set(banned);
let sum = 0;
let ans = 0;
for (let i = 1; i <= n; i++) {
if (i + sum > maxSum) {
break;
}
if (set.has(i)) {
continue;
}
sum += i;
ans++;
}
return ans;
}func maxCount(banned []int, n int, maxSum int) (ans int) {
ban := map[int]bool{}
for _, x := range banned {
ban[x] = true
}
s := 0
for i := 1; i <= n && s+i <= maxSum; i++ {
if !ban[i] {
ans++
s += i
}
}
return
}use std::collections::HashSet;
impl Solution {
pub fn max_count(banned: Vec<i32>, n: i32, max_sum: i32) -> i32 {
let mut set = banned.into_iter().collect::<HashSet<i32>>();
let mut sum = 0;
let mut ans = 0;
for i in 1..=n {
if sum + i > max_sum {
break;
}
if set.contains(&i) {
continue;
}
sum += i;
ans += 1;
}
ans
}
}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:
func maxCount(banned []int, n int, maxSum int) (ans int) {
banned = append(banned, []int{0, n + 1}...)
sort.Ints(banned)
ban := []int{}
for i, x := range banned {
if (i > 0 && x == banned[i-1]) || x > n+1 {
continue
}
ban = append(ban, x)
}
for k := 1; k < len(ban); k++ {
i, j := ban[k-1], ban[k]
left, right := 0, j-i-1
for left < right {
mid := (left + right + 1) >> 1
if (i+1+i+mid)*mid/2 <= maxSum {
left = mid
} else {
right = mid - 1
}
}
ans += left
maxSum -= (i + 1 + i + left) * left / 2
if maxSum <= 0 {
break
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) for sorting. |
| Greedy Approach without Sorting | Time Complexity: O(n). |
| Greedy + Enumeration | – |
| Greedy + Binary Search | – |
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. |
Frequently asked questions
Is Maximum Number of Integers to Choose From a Range I easy or hard?
The problem is generally considered medium difficulty because the greedy insight is simple but easy to overlook initially. Once you realize selecting the smallest valid integers maximizes the count under a sum constraint, the implementation becomes straightforward.
Maximum Number of Integers to Choose From a Range I Python/Java solution
In Python or Java, create a set from the banned array, iterate numbers from 1 to n, skip banned values, and accumulate the sum until it exceeds maxSum. Increment a counter for each valid selection. The algorithm remains O(n + b) regardless of language.
How to solve Maximum Number of Integers to Choose From a Range I in O(n)?
Insert all banned numbers into a hash set, then iterate from 1 to n. Skip any value present in the set. Maintain a running sum and stop when adding the current number would exceed maxSum. This greedy process ensures you pick the smallest valid integers first and runs in linear time relative to the range.
What is the best approach for Maximum Number of Integers to Choose From a Range I?
The best approach is a greedy strategy combined with a hash set. Store banned numbers in a set, iterate from 1 to n, and keep adding numbers while the running sum stays ≤ maxSum. Because smaller integers consume less sum, choosing them first maximizes the count. This solution runs in O(n + b) time and O(b) space.
Is Maximum Number of Integers to Choose From a Range I asked at Google/Amazon/Meta?
Greedy selection and constraint-based counting problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. The problem tests understanding of greedy reasoning, hash sets, and early termination conditions when working with sum constraints.
What data structure is used in Maximum Number of Integers to Choose From a Range I?
The primary data structure is a hash set to store banned numbers for constant-time membership checks. Some implementations also use sorting with pointers or binary search, but the hash set approach is usually simpler and faster.
What is the time complexity of Maximum Number of Integers to Choose From a Range I?
The optimal solution runs in O(n + b) time where n is the range limit and b is the number of banned values. A hash set enables O(1) membership checks while iterating through numbers from 1 to n. The space complexity is O(b) to store banned numbers.