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

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.