Skip to main content
Talentd

Maximum Number of Integers to Choose From a Range II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchGreedySorting8 min readAsked at: PayPal
Practice this problem

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,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 10, which does not exceed maxSum.

 

Constraints:

  • 1 <= banned.length <= 105
  • 1 <= banned[i] <= n <= 109
  • 1 <= maxSum <= 1015

Approach Overview

Problem Overview: You need to choose as many integers as possible from the range [1, n] while avoiding values in the banned array. The chosen numbers must also satisfy sum ≤ maxSum. The goal is to maximize the count of chosen integers.

Approach 1: Greedy Iteration Over the Range (O(n) time, O(m) space)

The direct strategy is greedy: always pick the smallest available integer because smaller numbers consume less of the maxSum budget. Store the banned values in a hash set, iterate from 1 to n, and skip numbers that appear in the set. For each allowed number, check whether adding it keeps the running sum ≤ maxSum. If it does, include it and increase the count.

This works because choosing smaller integers maximizes how many numbers you can include before hitting the sum limit. However, when n is very large, iterating through the entire range becomes inefficient. The algorithm runs in O(n) time with O(m) extra space for the banned set.

Approach 2: Deduplication + Sorting + Binary Search (O(m log m) time, O(m) space)

A more scalable solution processes only the banned numbers instead of scanning the entire range. First remove duplicates from banned, filter values greater than n, and sort the remaining list. These banned numbers split the range [1, n] into valid segments where numbers can be chosen freely.

For each valid segment, compute how many numbers you can take without exceeding maxSum. Instead of iterating through every integer, use the arithmetic series formula to compute the sum of a prefix of the segment. Apply binary search to determine the maximum count of numbers you can include from that segment while keeping the total sum within the budget.

This approach leverages sorting to organize banned values and a greedy strategy to always prioritize smaller numbers. By operating on segments instead of individual integers, the algorithm reduces the complexity to O(m log m), where m is the size of the banned array. The space complexity remains O(m) due to storing and sorting the filtered banned list.

Recommended for interviews: Interviewers expect the greedy insight: always take the smallest valid numbers first. Demonstrating the simple iteration approach shows understanding of the greedy principle. The optimized solution using deduplication, sorting, arithmetic sums, and binary search shows strong algorithmic thinking and handles large constraints efficiently.

Solution

We can add 0 and n + 1 to the array banned, then deduplicate and sort the array banned.

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Iteration with Hash SetO(n)O(m)When n is small and direct iteration over the range is affordable
Deduplication + Sorting + Binary SearchO(m log m)O(m)Large n with relatively small banned array; optimal scalable solution

Video Solution

【每日一题】LeetCode 2557. Maximum Number of Integers to Choose From a Range II • Huifeng Guan • 325 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximum Number of Integers to Choose From a Range II easy or hard?
Maximum Number of Integers to Choose From a Range II is rated Medium difficulty on LeetCode. The greedy insight is straightforward, but handling very large ranges efficiently requires sorting banned numbers and using arithmetic series calculations instead of iterating through every integer.
Maximum Number of Integers to Choose From a Range II Python/Java solution
Typical implementations first deduplicate and sort the banned list, then iterate through allowed ranges while calculating arithmetic sums. Python, Java, C++, and Go solutions all follow the same logic: compute segment bounds, apply binary search to find the maximum valid count, and update the remaining sum budget.
How to solve Maximum Number of Integers to Choose From a Range II in O(n)?
Use a greedy scan from 1 to n while skipping banned values stored in a hash set. Add each allowed number to a running sum and stop once adding the next number would exceed maxSum. This approach runs in O(n) time and O(m) space, but it is only practical when n is relatively small.
What is the best approach for Maximum Number of Integers to Choose From a Range II?
The most efficient approach uses a greedy strategy combined with deduplication, sorting, and binary search. After sorting the banned numbers, treat the gaps between them as valid segments and compute how many integers can be taken from each segment without exceeding maxSum. Using arithmetic series sums and binary search keeps the complexity at O(m log m), where m is the size of the banned array.
Is Maximum Number of Integers to Choose From a Range II asked at Google/Amazon/Meta?
Problems combining greedy selection, range processing, and prefix sum math are common in interviews at companies like Amazon and Google. Variants of this problem test whether candidates recognize that choosing the smallest numbers first maximizes the count under a sum constraint.
What data structure is used in Maximum Number of Integers to Choose From a Range II?
Common data structures include a hash set for quick banned-number checks and a sorted array for processing banned values in order. Sorting allows you to identify valid number ranges, while binary search helps determine how many numbers can be taken from each range without exceeding the sum limit.
What is the time complexity of Maximum Number of Integers to Choose From a Range II?
The optimized solution runs in O(m log m) time due to sorting the banned array and performing binary searches within valid segments. The space complexity is O(m) for storing the filtered banned numbers. A simpler greedy iteration approach takes O(n) time, which can be too slow when n is very large.

Ready to solve this problem?

Practice Maximum Number of Integers to Choose From a Range II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Append K Integers With Minimal Sum

Next

Find All Numbers Disappeared in an Array