Maximum Number of Integers to Choose From a Range II - Video Solutions
【每日一题】LeetCode 2557. Maximum Number of Integers to Choose From a Range II
Maximum Number of Integers to Choose From a Range II - Video Solution
Watch 2 video solutions for Maximum Number of Integers to Choose From a Range II, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by Huifeng Guan has 325 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= banned[i] <= n <= 1091 <= 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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Iteration with Hash Set | O(n) | O(m) | When n is small and direct iteration over the range is affordable |
| Deduplication + Sorting + Binary Search | O(m log m) | O(m) | Large n with relatively small banned array; optimal scalable solution |