LeetCode 2557 - Maximum Number of Integers to Choose From a Range II

LeetCode Problem 2557

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Greedy, Sorting

Solution

Problem Understanding

The problem is asking to select the maximum number of integers from the range [1, n] under several constraints. First, integers in the banned array cannot be chosen. Second, each integer can be chosen at most once. Third, the sum of all chosen integers must not exceed maxSum. The goal is to determine the largest possible count of integers that satisfy all these conditions.

The input consists of three main components: banned, an array of integers that cannot be selected; n, which sets the upper bound of the selectable integers; and maxSum, which limits the total sum of the selected numbers. The output is a single integer representing the maximum count of valid integers.

Constraints give us important insights. The length of banned can be up to 10^5, the value of n can be up to 10^9, and maxSum can be as large as 10^15. This indicates that a naive approach iterating from 1 to n and checking conditions will be inefficient due to the large possible value of n. The problem guarantees positive integers, so we do not have to handle zero or negative numbers, but we do need to handle potentially very large sums and ranges.

Edge cases to consider include: banned containing all small numbers, maxSum being very small relative to n, or the banned list being empty. These edge cases could affect both correctness and efficiency.

Approaches

A brute-force approach would be to iterate over every number from 1 to n, check whether it is banned, and whether adding it keeps the sum below maxSum. If both conditions are satisfied, include it in the result. This approach is correct because it checks all possibilities in order, but it is computationally infeasible because iterating up to 10^9 is too slow.

The optimal approach leverages the fact that the smallest non-banned integers contribute the least to the sum. Therefore, if we sort the non-banned integers and pick them greedily from smallest to largest until adding the next would exceed maxSum, we will maximize the count. Using a hash set for banned numbers allows for O(1) lookups, and iterating only over non-banned numbers up to either n or the point where the sum exceeds maxSum keeps the algorithm efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(b)	Iterates all numbers up to n, checks banned list each time
Optimal	O(b + k)	O(b)	Use hash set for banned, iterate over valid numbers until maxSum is reached, where k is the number of numbers actually selected

Algorithm Walkthrough

1. Convert the banned array into a hash set for O(1) membership checks. This avoids repeated linear searches.
2. Initialize current_sum to zero and count to zero. These will track the sum of selected numbers and the number of integers chosen, respectively.
3. Iterate over integers i from 1 to n in ascending order. We start from 1 because smaller numbers allow us to maximize the count under a sum constraint.
4. For each integer, check if it is in the banned set. If it is banned, skip it.
5. If it is not banned, check if adding it to current_sum would exceed maxSum. If yes, stop the iteration as any larger numbers would only increase the sum further.
6. If adding the number does not exceed maxSum, increment count and add the number to current_sum.
7. Continue until all numbers up to n are processed or the sum limit is reached.
8. Return count as the maximum number of integers that can be chosen.

The algorithm works because it always chooses the smallest available numbers first. Since the sum constraint is additive and all numbers are positive, picking smaller numbers first ensures that the sum is maximized in terms of count. Using a hash set guarantees O(1) lookups to avoid banned numbers.

Python Solution

from typing import List

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned_set = set(banned)
        current_sum = 0
        count = 0
        
        for i in range(1, n + 1):
            if i in banned_set:
                continue
            if current_sum + i > maxSum:
                break
            current_sum += i
            count += 1
        
        return count

The Python implementation first converts the banned list into a set for fast lookups. It initializes two variables, current_sum and count. Then it iterates over all numbers from 1 to n. If a number is banned, it is skipped. If adding the number exceeds maxSum, the loop breaks early. Otherwise, the number is added to the sum and the count is incremented. Finally, count is returned as the result.

Go Solution

func maxCount(banned []int, n int, maxSum int64) int {
    bannedSet := make(map[int]struct{})
    for _, num := range banned {
        bannedSet[num] = struct{}{}
    }
    
    var currentSum int64 = 0
    count := 0
    
    for i := 1; i <= n; i++ {
        if _, exists := bannedSet[i]; exists {
            continue
        }
        if currentSum+int64(i) > maxSum {
            break
        }
        currentSum += int64(i)
        count++
    }
    
    return count
}

The Go implementation mirrors the Python solution. It uses a map[int]struct{} as a set to store banned numbers. Variables currentSum and count are initialized to track the sum and the number of integers selected. Iteration over integers is done from 1 to n. The type int64 is used for the sum to prevent overflow since maxSum can be very large.

Worked Examples

Example 1: banned = [1,4,6], n = 6, maxSum = 4

i	Banned?	current_sum	count	Action
1	yes	0	0	skip
2	no	0	0	add 2 → sum=2, count=1
3	no	2	1	add 3 → sum=5 > maxSum → break

Result: 1

Example 2: banned = [4,3,5,6], n = 7, maxSum = 18

i	Banned?	current_sum	count	Action
1	no	0	0	add 1 → sum=1, count=1
2	no	1	1	add 2 → sum=3, count=2
3	yes	3	2	skip
4	yes	3	2	skip
5	yes	3	2	skip
6	yes	3	2	skip
7	no	3	2	add 7 → sum=10, count=3

Result: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(b + k)	O(b) to build banned set, O(k) to iterate over non-banned numbers until sum reaches maxSum, where k is the count of selected numbers
Space	O(b)	Storage for banned set

The time complexity is efficient because we avoid iterating up to n when maxSum is small and we skip banned numbers efficiently using a set. Space complexity is linear in the size of the banned list.

Test Cases

# Provided examples
assert Solution().maxCount([1,4,6], 6, 4) == 1  # Example 1
assert Solution().maxCount([4,3,5,6], 7, 18) == 3  # Example 2

# Edge cases
assert Solution().maxCount([], 5, 15) == 5  # No banned numbers, sum allows all
assert Solution().maxCount([1,2,3,4,5], 5, 10) == 0  # All small numbers banned
assert Solution().maxCount([100000], 1000000, 1) == 1  # maxSum too small
assert Solution().maxCount([1], 1, 1) == 0  # Only number banned
assert Solution().maxCount([], 1000, 1) == 1  # maxSum smaller than first few numbers

Test	Why
[1,4,6], 6, 4	Basic example with banned numbers
[4,3,5,6], 7, 18	Skips multiple banned numbers, sum allows some larger numbers
[], 5, 15	No banned numbers, sum allows all numbers
[1,2,3,4,5], 5, 10	All small numbers banned, cannot pick any
[100000], 1000000,