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.

Description Hints 3 Solution Video 11:46

2554. Maximum Number of Integers to Choose From a Range I

Medium68.0% acceptance1 company

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 <= 10⁴
1 <= banned[i], n <= 10⁴
1 <= maxSum <= 10⁹

Asked at 1 company

PayPal

Topics

Hints open one at a time

Hint 1

Keep the banned numbers that are less than or equal to n in a set.

Hint 2

Loop over the numbers from 1 to n and if the number is not banned, use it.

Hint 3

Keep adding numbers while they are not banned, and their sum is less than or equal to k.

11:46

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution