BEATS 100% ❤️‍🔥 DETAILED DRY RUN ❤️‍🔥 MILDLY AROUSING 🤤🤤
Intuition\n\nThe problem involves determining the maximum count of numbers that can be selected from 1 to n such that:\n1. The selected numbers are not in the b
### **Intuition**\n\nThe problem involves determining the maximum count of numbers that can be selected from `1` to `n` such that:\n1. The selected numbers are not in the `banned` list.\n2. The sum of the selected numbers does not exceed `maxSum`.\n\nThe algorithm works by iterating over the numbers from `1` to `n` and adding a number to the selection if:\n1. The number is not present in the `banned` list.\n2. Adding the number does not exceed `maxSum`.\n\nBy leveraging a lookup array (`bannedArr`) to check if a number is banned, the solution optimizes the banning check to O(1) time complexity per number.\n\n---\n\n### **Detailed Step-by-Step Approach**\n\n1. **Convert `banned` List to a Lookup Array**:\n   - Create an array `bannedArr` of size `10001` (since the numbers are small and bounded).\n   - Mark the indices corresponding to numbers in `banned` with `1`. For example, if `banned = [2, 4]`, then `bannedArr[2] = 1` and `bannedArr[4] = 1`.\n\n2. **Initialize Counters**:\n   - `count`: To keep track of the number of valid numbers selected.\n   - `sum`: To store the cumulative sum of the selected numbers.\n\n3. **Iterate Through Numbers**:\n   - Loop from `1` to `n`:\n     - If the current number `i` is in the `bannedArr`, skip it.\n     - Check if adding `i` to `sum` exceeds `maxSum`. If it does, break the loop.\n     - Otherwise, include `i` in the count and update the `sum`.\n\n4. **Return the Result**:\n   - After exiting the loop, return `count`, which represents the maximum count of numbers that can be selected.\n\n---\n\n### **Dry Run with Detailed Example**\n\n#### Input:\n```text\nbanned = [2, 4]\nn = 5\nmaxSum = 7\n```\n\n#### Execution Trace:\n\n| Step | `i` (Current Number) | `bannedArr[i]` | `sum` Before | `sum + i` | Action                         | `count` | `sum` After |\n|------|-----------------------|----------------|--------------|-----------|--------------------------------|---------|-------------|\n| 1    | 1                     | 0              | 0            | 1         | Add `i` to selection           | 1       | 1           |\n| 2    | 2                     | 1              | 1            | -         | Skip (banned)                  | 1       | 1           |\n| 3    | 3                     | 0              | 1            | 4         | Add `i` to selection           | 2       | 4           |\n| 4    | 4                     | 1              | 4            | -         | Skip (banned)                  | 2       | 4           |\n| 5    | 5                     | 0              | 4            | 9         | Break (exceeds `maxSum`)       | 2       | 4           |\n\n#### Output:\n```text\n2\n```\n\n---\n\n### **Time Complexity**\n\n1. **Building the Lookup Array**:\n   - Iterating over the `banned` array takes O(b), where `b` is the size of the `banned` array.\n\n2. **Iterating Through Numbers**:\n   - Looping through numbers from `1` to `n` takes O(n).\n\n3. **Overall Complexity**:\n   - **Time Complexity**: O(b + n), where `b` is the size of `banned` and `n` is the upper limit of the range.\n   - **Space Complexity**: O(1), as the `bannedArr` is a fixed-size array of length 10001.\n\n---\n\n### **Code**\n\n\n\n```java\nclass Solution {\n\n    public int maxCount(int[] banned, int n, int maxSum) {\n\n        // Create a lookup array for banned numbers\n        int[] bannedArr = new int[10001];\n        for (int ban : banned) {\n            bannedArr[ban] = 1; // Mark banned numbers\n        }\n\n        // Initialize counters\n        int count = 0;\n        int sum = 0;\n\n        // Iterate through numbers from 1 to n\n        for (int i = 1; i <= n; i++) {\n            \n            // Check if the current number is banned\n            if (bannedArr[i] == 1) continue;\n\n            // Check if adding the current number exceeds maxSum\n            if (sum + i > maxSum) break;\n\n            // Add the current number to the selection\n            count++;\n            sum += i;\n        }\n\n        // Return the maximum count of valid numbers\n        return count;\n    }\n}\n```\n\n---\n\n### **Key Takeaways**\n1. The use of a lookup array ensures efficient checks for banned numbers.\n2. The algorithm greedily selects numbers starting from the smallest to maximize the count while staying under `maxSum`.\n3. It achieves optimal time and space complexity, suitable for handling larger inputs efficiently.\n---\n![Screenshot from 2024-07-09 09-56-34.png](https://assets.leetcode.com/users/images/9ae55e8c-9f93-4cba-abad-7a7d5e26b3da_1733473072.0723426.png)\n
['Hash Table', 'Greedy', 'Java']