Easy beats 97% || 3 Ways || Frequency Count || Map || Set
\n\n\n# Approach (Map)\n\n#### Steps:\n\nPopulate the Map (mp):\n\nIterate through the banned array and add its elements as keys to the map.\nThis step ensures 
![image.png](https://assets.leetcode.com/users/images/94ac7e1d-c574-4e12-b34d-433ed65f402c_1733475270.0932305.png)\n\n\n# Approach (Map)\n\n#### Steps:\n\n**Populate the Map (mp):**\n\nIterate through the **banned array** and add its elements as **keys** to the **map**.\nThis step ensures we can quickly check if a number is banned.\n\nFor each number **\uD835\uDC56** from **1** to **\uD835\uDC5B**:\n\n- **Check if it\u2019s not banned:**\n-      mp[i] < 1: If \uD835\uDC56 is not in the banned map, proceed.\n\n- **Check if adding \uD835\uDC56 keeps the sum within maxSum:**\n-       currSum + i <= maxSum: Ensures the sum constraint is met.\n- **If both conditions are true:**\n-       Increment the result (res) and add \uD835\uDC56 to currSum.\n- **Early Exit Condition:**\n-     If currSum == maxSum or adding the next number will exceed maxSum, break out of the loop early.\n\n\n# Complexity\n- Time complexity: **O(n+m)**, where **\uD835\uDC5A** is the size of the banned array\n- Space complexity: **O(m)**\n\n# Code (Map)\n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        int res = 0, currSum = 0;\n        unordered_map<int, int> mp;\n        for(int i = 0; i<banned.size(); i++){\n            mp[banned[i]]++;\n        }\n\n        for(int i = 1 ; i<=n ; i++){\n            if(mp[i] < 1 && currSum + i <= maxSum){\n                res++;\n                currSum += i;\n            }\n            if(currSum == maxSum || currSum + i > maxSum) break;\n        }\n        return res;\n    }\n};\n```\n\n# Approach (Set)\n-  Create an **unordered_set** from the banned array for **\uD835\uDC42(1)** average-time lookups.\n- Iterate through numbers **\uD835\uDC56** = **1** to **\uD835\uDC5B**:\n    - If **\uD835\uDC56** is not in the banned set and adding **\uD835\uDC56** to **currSum** doesn\'t exceed **maxSum**, include **\uD835\uDC56** in the result (**res**) and update **currSum**.\n- Return the count of valid integers (**res**) after completing the iteration.\n# Code(Set)\n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        unordered_set<int> bannedSet(banned.begin(), banned.end());\n        int res = 0, currSum = 0;\n        for (int i = 1; i <= n; i++) {\n            if (bannedSet.find(i) == bannedSet.end() && currSum + i <= maxSum) {\n                res++;\n                currSum += i;   \n            }\n            if(currSum == maxSum || currSum + i > maxSum) break;\n        }\n\n        return res;\n    }\n};\n```\n\n# Code (Frequency Array)\n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        vector<bool> isBanned(n + 1, 0); \n        for (int num : banned) {\n            if (num <= n) { \n                isBanned[num] = 1;\n            }\n        }\n        int res = 0, currSum = 0;\n        for (int i = 1; i <= n; i++) {\n            if (!isBanned[i] && currSum + i <= maxSum) {\n                res++;\n                currSum += i;\n            }\n        }\n\n        return res;\n    }\n};\n\n```
['Ordered Map', 'Ordered Set', 'C++']