What is the time complexity of LeetCode 2554. Maximum Number of Integers to Choose From a Range I?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2554. Maximum Number of Integers to Choose From a Range I?

The Python solution on this page uses O(n) auxiliary space.

Maximum Number of Integers to Choose From a Range I — LeetCode 2554 Python Solution

MediumGreedyArrayHash TableBinary SearchSorting

Problem: #2554
Pattern: Binary Search
Reading time: 2 min
Source: leetcode.com

The problem

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].

Example

Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation: You can choose the integers 2 and 4.

Python solution

Python

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        ans = s = 0
        ban = set(banned)
        for i in range(1, n + 1):
            if s + i > maxSum:
                break
            if i not in ban:
                ans += 1
                s += i
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 2554. Maximum Number of Integers to Choose From a Range I is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2554. Maximum Number of Integers to Choose From a Range I?: LeetCode 2554. Maximum Number of Integers to Choose From a Range I is rated Medium on LeetCode.
What is the time complexity of LeetCode 2554. Maximum Number of Integers to Choose From a Range I?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2554. Maximum Number of Integers to Choose From a Range I?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2554. Maximum Number of Integers to Choose From a Range I cover?: LeetCode 2554. Maximum Number of Integers to Choose From a Range I is tagged Greedy, Array, Hash Table, Binary Search and Sorting on LeetCode.