✅ Easy to Understand Intuitive approach | Greedy Thinking | Detailed Video explanation 🔥🔥
Intuition\nThe problem requires us to select the maximum count of numbers from the range [1, n] such that their sum does not exceed maxSum while skipping the ba
# Intuition\nThe problem requires us to select the maximum count of numbers from the range `[1, n]` such that their sum does not exceed `maxSum` while skipping the banned numbers. The greedy approach naturally fits here: prioritize smaller numbers first to maximize the count, as smaller numbers contribute less to the sum.\n\n# Approach\n1. **Store Banned Numbers**: Use a `HashSet` to store all banned numbers for O(1) look-up.\n2. **Iterate Through Numbers**: Start from 1 and proceed to `n`. Skip any number present in the banned set.\n3. **Check Sum Constraint**: For each non-banned number, check if adding it to the current sum exceeds `maxSum`. If it does, return the count of numbers selected so far.\n4. **Update Sum and Counter**: If the number does not exceed the `maxSum`, add it to the current sum and increment the counter.\n5. **Return Final Count**: If the loop completes, return the count of selected numbers.\n\n# Complexity\n- **Time complexity**:  \n  $$O(n)$$  \n  - Iterating through the range `[1, n]` takes O(n).  \n  - Checking if a number is in the set takes O(1) per number, so the overall time complexity is O(n).\n\n- **Space complexity**:  \n  $$O(m)$$  \n  - Storing `m` banned numbers in a `HashSet` takes O(m) space, where `m` is the length of the `banned` array.\n\n\n# Code\n```java []\nclass Solution {\n    public int maxCount(int[] banned, int n, int maxSum) {\n        // Create a set to store banned numbers for O(1) look-up\n        Set<Integer> set = new HashSet<>();\n        for (int x : banned) {\n            set.add(x); // Add each banned number to the set\n        }\n\n        int csum = 0; // Current sum of selected numbers\n        int counter = 0; // Count of selected numbers\n\n        // Iterate through numbers from 1 to n\n        for (int i = 1; i <= n; i++) {\n            // Skip the number if it is in the banned set\n            if (set.contains(i)) continue;\n\n            // Check if adding the current number exceeds maxSum\n            if (csum + i > maxSum) {\n                return counter; // Return the count if maxSum is exceeded\n            }\n\n            // Add the current number to the sum and increment the count\n            csum += i;\n            counter++;\n        }\n\n        // Return the total count of numbers that can be selected\n        return counter;\n    }\n}\n\n```\n\nhttps://youtu.be/qsxh4rDtXyo
['Array', 'Hash Table', 'Greedy', 'Java']