• Leetcode POTDs

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

Problem Statement

Link - Problem 2554

Question

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 <= 104
• 1 <= banned[i], n <= 104
• 1 <= maxSum <= 109

Solution

class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        vector<bool>valid(1e4+1,true);

        for(auto it:banned)
            valid[it] = false;

        n=n+1;
        int count = 0;

        for(int i = 1; i<n;i++){
            if(!valid[i])
                continue;

            if(maxSum>=i){
                maxSum-=i;
                count++;
            }
        }

        return count;
    }
};

Complexity Analysis

| Algorithm    | Time Complexity | Space Complexity |
| ------------ | --------------- | ---------------- |
| Linear Sweep | O(b+n)          | O(n+b)           |

Explanation

Intial Thoughts

First, understand the rules for choosing integers. Visualize a grid of numbers from 1 to n and cross out the banned ones. The goal is to pick as many numbers as possible without exceeding maxSum. Separate the banned numbers from the valid ones. Create a list or array to keep track of valid numbers.

Intuitive Analysis

Start from the smallest valid number and keep adding it to the running total until it reaches maxSum. Think of this process as pouring water into a jar - we fill the jar with the smallest amounts first. If a number exceeds maxSum, we stop and return the current count of valid numbers. Imagine the count as the number of ‘stones’ we’ve added to our jar, where each stone represents a valid number. This approach ensures we make the most of the sum limit while adhering to the rules.

1. Intuition

• The problem can be solved by iterating through the range [1, n] and checking if each number is not in the banned array.
• We need to keep track of the sum of the chosen numbers to ensure it does not exceed maxSum.
• The key insight is to start from the smallest number and keep adding it to the sum until we reach maxSum.
• This greedy approach works because we are trying to maximize the count of chosen numbers.
• By choosing the smallest numbers first, we are maximizing the count of chosen numbers.
• This approach also ensures that we do not exceed maxSum.
• The time complexity of this approach is O(n) because we are iterating through the range [1, n] once.

2. Implementation

• Create a boolean array valid of size 1e4+1 to keep track of banned numbers, vector<bool>valid(1e4+1,true);
• Mark banned numbers as false in the valid array, for(auto it:banned) valid[it] = false;
• Initialize count to 0 and iterate through the range [1, n], int count = 0; for(int i = 1; i<n;i++)
• If the current number is not banned and does not exceed maxSum, add it to the sum and increment count, if(maxSum>=i){ maxSum-=i; count++; }
• Return the count of chosen numbers, return count;
• The space complexity is O(n) because of the valid array.
• The time complexity is O(n) because of the iteration through the range [1, n].

Complexity Analysis

Time Complexity:

• The time complexity of the given algorithm revolves around two primary loops: one for marking banned numbers, and the other for the linear sweep through numbers 1 to n. The first loop iterates over banned numbers, taking O(b) time, where b is the number of elements in the banned array.
• The subsequent linear sweep for(int i = 1; i<n;i++) dominates with O(n) time complexity. This is because the loop iterates over numbers 1 to n, performing constant-time operations within the loop.
• Considering both operations are performed sequentially, the overall time complexity is O(b + n). This classification captures the dominant linear sweep through the number space, impacted by the initial marking of banned numbers.

Space Complexity:

• The space complexity of the algorithm primarily stems from the usage of a valid vector with size 1e4+1. This array is used to mark valid numbers, resulting in a memory usage proportional to its size.
• Additionally, the storage of banned numbers can contribute to the overall space complexity. This takes up space proportional to b, the number of banned numbers.
• Combining these insights, the space complexity is O(n + b), which captures both the fixed allocation for the valid array and the size-dependent contribution of the banned array.

Footnote

This question is rated as Medium difficulty.

Hints

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

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

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

Similar Questions: