🚀 "Mastering Maximum Count of Integers: Map, Binary Search, and Two-Pointer Techniques 🌟
Select Maximum Integers Following Rules \uD83D\uDE80  \n\nIn this article, we\u2019ll explore three different solutions to solve the problem of selecting the ma
### Select Maximum Integers Following Rules \uD83D\uDE80  \n\nIn this article, we\u2019ll explore **three different solutions** to solve the problem of selecting the maximum number of integers from the range **[1, n]** that adhere to the following rules:  \n\n1. **The integers should not appear in the banned list.**  \n2. **The sum of chosen integers should not exceed maxSum.**  \n3. **Each integer can only be chosen once.**  \n\nWe\u2019ll discuss three unique approaches:  \n1. **Using a Hash Map for Quick Lookup.**  \n2. **Using Binary Search for Optimization.**  \n3. **Using a Two-Pointer Technique for Efficient Processing.**\n\n---\n\n# Complexity Overview \u23F3  \n| Approach         | Time Complexity | Space Complexity |  \n|------------------|----------------|------------------|  \n| Hash Map         | $$O(n + b)$$  | $$O(b)$$         |  \n| Binary Search    | $$O(b \\cdot \\log(b) + n \\cdot \\log(b))$$ | $$O(1)$$   |  \n| Two-Pointer      | $$O(b \\cdot \\log(b) + n)$$ | $$O(1)$$         |  \n\nWhere $$n$$ is the size of the range, and $$b$$ is the size of the banned list.  \n\n---\n![c1ee5054-dd07-4caa-a7df-e21647cfae9e_1709942227.5165014.png](https://assets.leetcode.com/users/images/ad2c9b9e-5789-47e2-a98d-bb54fcc2e1dd_1733461330.5835323.png)\n\n# **Solution 1: Hash Map Approach** \uD83D\uDDC2\uFE0F  \n\n## Idea \uD83D\uDCA1  \n1. Use a **hash map** to mark all banned numbers for quick lookup.  \n2. Iterate through the range **[1, n]**, and skip any number in the banned list.  \n3. Keep a running sum, and stop if adding the current number exceeds **maxSum**.  \n\n# Code \uD83D\uDCBB  \n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        unordered_map<int, int> mp;\n        for (int i : banned) {\n            mp[i]++;\n        }\n\n        int sum = 0, res = 0;\n        for (int i = 1; i <= n; i++) {\n            if (!mp[i]) { // If not banned\n                sum += i;\n                if (sum <= maxSum) {\n                    res++;\n                } else {\n                    return res; // Stop as remaining values will also exceed maxSum\n                }\n            }\n        }\n        return res;\n    }\n};\n```\n```python []\nclass Solution:\n    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n        mp = defaultdict(int)\n        for i in banned:\n            mp[i] += 1\n\n        sum_ = 0\n        res = 0\n\n        for i in range(1, n + 1):\n            if not mp[i]:\n                sum_ += i\n                if sum_ <= maxSum:\n                    res += 1\n                else:\n                    return res\n\n        return res\n```\n```java []\nclass Solution {\n    public int maxCount(int[] banned, int n, int maxSum) {\n        HashMap<Integer, Integer> mp = new HashMap<>();\n        for (int i : banned) {\n            mp.put(i, 1);\n        }\n        int sum = 0, res = 0;\n        for (int i = 1; i <= n; i++) {\n            if (!mp.containsKey(i)) {\n                sum += i;\n                if (sum <= maxSum) {\n                    res++;\n                } else {\n                    return res;\n                }\n            }\n        }\n        return res;\n    }\n}\n```\n``` javascript []\nvar maxCount = function(banned, n, maxSum) {\n    let mp = new Map();\n    for (let i of banned) {\n        mp.set(i, 1);\n    }\n    let sum = 0, res = 0;\n    for (let i = 1; i <= n; i++) {\n        if (!mp.has(i)) {\n            sum += i;\n            if (sum <= maxSum) {\n                res++;\n            } else {\n                return res;\n            }\n        }\n    }\n    return res;\n};\n```\n\n# Complexity \u23F3  \n- **Time**: $$O(n + b)$$ (Marking banned numbers + Iterating through range).  \n- **Space**: $$O(b)$$ for the hash map.  \n\n---\n\n# **Solution 2: Binary Search Approach** \uD83D\uDD0D  \n\n## Idea \uD83D\uDCA1  \n1. **Sort** the banned list for efficient lookups.  \n2. Iterate through **[1, n]**, and use **binary search** to skip banned numbers.  \n3. Track the running sum and terminate if it exceeds **maxSum**.  \n\n# Code \uD83D\uDCBB  \n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        sort(banned.begin(), banned.end());\n        int sum = 0, res = 0;\n\n        for (int i = 1; i <= n; i++) {\n            if (!binary_search(banned.begin(), banned.end(), i)) { // Check banned\n                sum += i;\n                if (sum <= maxSum) {\n                    res++;\n                } else {\n                    return res; // Stop as all further sums will exceed maxSum\n                }\n            }\n        }\n        return res;\n    }\n};\n```\n```python []\nclass Solution:\n    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:\n        banned.sort()\n        total = 0\n        count = 0\n        for i in range(1, n + 1):\n            if not self.binary_search(banned, i):\n                total += i\n                if total <= maxSum:\n                    count += 1\n                else:\n                    break\n        return count\n\n    def binary_search(self, arr, target):\n        left, right = 0, len(arr) - 1\n        while left <= right:\n            mid = (left + right) // 2\n            if arr[mid] == target:\n                return True\n            elif arr[mid] < target:\n                left = mid + 1\n            else:\n                right = mid - 1\n        return False\n```\n```java []\nclass Solution {\n    public int maxCount(int[] banned, int n, int maxSum) {\n        Arrays.sort(banned);\n        int total = 0, count = 0;\n        for (int i = 1; i <= n; i++) {\n            if (!binarySearch(banned, i)) {\n                total += i;\n                if (total <= maxSum) count++;\n                else break;\n            }\n        }\n        return count;\n    }\n\n    private boolean binarySearch(int[] arr, int target) {\n        int left = 0, right = arr.length - 1;\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n            if (arr[mid] == target) return true;\n            if (arr[mid] < target) left = mid + 1;\n            else right = mid - 1;\n        }\n        return false;\n    }\n}\n\n```\n```javascript []\n// Solution 2: Using Binary Search\nvar maxCount = function(banned, n, maxSum) {\n    banned.sort((a, b) => a - b);\n    let total = 0, count = 0;\n    for (let i = 1; i <= n; i++) {\n        if (!binarySearch(banned, i)) {\n            total += i;\n            if (total <= maxSum) count++;\n            else break;\n        }\n    }\n    return count;\n};\n\nfunction binarySearch(arr, target) {\n    let left = 0, right = arr.length - 1;\n    while (left <= right) {\n        let mid = Math.floor((left + right) / 2);\n        if (arr[mid] === target) return true;\n        if (arr[mid] < target) left = mid + 1;\n        else right = mid - 1;\n    }\n    return false;\n}\n```\n\n# Complexity \u23F3  \n- **Time**: $$O(b \\cdot \\log(b) + n \\cdot \\log(b))$$ (Sorting + Binary searching for every number).  \n- **Space**: $$O(1)$$ (No extra space required).  \n\n---\n\n# **Solution 3: Two-Pointer Approach** \uD83D\uDD04  \n\n## Idea \uD83D\uDCA1  \n1. **Sort** the banned list and use a pointer to track the banned elements.  \n2. Iterate through **[1, n]** and compare each number to the current banned number.  \n3. Skip numbers in the banned list using the pointer, and add other numbers to the sum.  \n\n\n# Code \uD83D\uDCBB  \n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        sort(banned.begin(), banned.end());\n        int sum = 0, res = 0, it = 0, len = banned.size();\n\n        for (int i = 1; i <= n; i++) {\n            if (it < len && banned[it] == i) {\n                while (it < len && banned[it] == i) {\n                    it++; // Skip banned numbers\n                }\n            } else {\n                sum += i;\n                if (sum <= maxSum) {\n                    res++;\n                } else {\n                    return res; // Stop as further numbers will exceed maxSum\n                }\n            }\n        }\n        return res;\n    }\n};\n```\n```python []\nclass Solution:\n    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:\n        banned.sort()\n        total = 0\n        count = 0\n        it = 0\n        for i in range(1, n + 1):\n            if it < len(banned) and banned[it] == i:\n                while it < len(banned) and banned[it] == i:\n                    it += 1\n            else:\n                total += i\n                if total <= maxSum:\n                    count += 1\n                else:\n                    break\n        return count\n```\n```java []\nclass Solution {\n    public int maxCount(int[] banned, int n, int maxSum) {\n        Arrays.sort(banned);\n        int total = 0, count = 0, it = 0;\n        for (int i = 1; i <= n; i++) {\n            if(it < banned.length && banned[it] == i){\n                while (it < banned.length && banned[it] == i){\n                    it++;\n                }\n            }\n            else{\n                total += i;\n                if (total <= maxSum) count++;\n                else break;\n            }\n        }\n        return count;\n    }\n}\n```\n```javascript []\nvar maxCount = function(banned, n, maxSum) {\n    banned.sort((a, b) => a - b);\n    let total = 0, count = 0, it = 0;\n    for (let i = 1; i <= n; i++) {\n        if(it < banned.length && banned[it] === i){\n            while(it < banned.length && banned[it] === i){\n                it++;   \n            }\n        }\n        else{\n            total += i;\n            if (total <= maxSum) count++;\n            else break;\n        }\n    }\n    return count;\n};\n\n```\n\n# Complexity \u23F3  \n- **Time**: $$O(b \\cdot \\log(b) + n)$$ (Sorting + Iterating through range).  \n- **Space**: $$O(1)$$ (No extra space required).  \n\n---\n\n# Comparison \u2696\uFE0F  \n\n| Approach         | Advantages                        | Disadvantages                    |  \n|------------------|-----------------------------------|-----------------------------------|  \n| **Hash Map**     | Quick lookups for banned numbers. | Extra space for the hash map.    |  \n| **Binary Search**| Efficient for large ranges.       | Slower than two-pointer.         |  \n| **Two-Pointer**  | Minimal space and faster runtime. | Requires sorted banned list.     |  \n\n---\n\n# Example Walkthrough \uD83D\uDCDD  \n\n## Input  \n```plaintext\nbanned = [2, 3, 4]  \nn = 10  \nmaxSum = 15  \n```\n\n## Output  \n```plaintext\n5  \n```\n\n## Explanation  \nThe numbers selected are **[1, 5, 6, 7, 8]**, whose sum is 15.  \n\n---\n\n# Final Thoughts \uD83D\uDCAD  \n\nEach of the three solutions has its strengths depending on the problem constraints:  \n- Use **Hash Map** for quick checks when space isn\'t a concern.  \n- Use **Binary Search** if the banned list is already sorted.  \n- Use **Two-Pointer** for the most optimized runtime and minimal memory usage.  \n\n**Which approach is your favorite? Let me know in the comments and don\u2019t forget to upvote if this helped! \uD83D\uDE80**\n\n![1HBC0324_COV.jpg](https://assets.leetcode.com/users/images/59e04527-5fa6-4594-870e-909daac96ac1_1733461238.1215591.jpeg)\n
['Array', 'Hash Table', 'Two Pointers', 'Binary Search', 'Greedy', 'Sorting', 'Python', 'C++', 'Java', 'JavaScript']