[C++ & Java] With & without unordered set - Explained
\n# Approach 1: O(N) space, O(N) time\nSimply put all banned items into a unordered set and then \nstrat from 1 to check each values present in set or not if no
\n# Approach 1: O(N) space, O(N) time\nSimply put all banned items into a unordered set and then \nstrat from 1 to check each values present in set or not if not \nthen count it and add it to sum.\n\n```cpp []\nint maxCount(vector<int>& banned, int n, int maxSum) {\n    int ans = 0;\n    unordered_set<int> s(begin(banned), end(banned));\n    for(int i = 1; i <= n; ++i){\n        if(s.find(i) == s.end() && maxSum - i >= 0) { ans++; maxSum -= i; }\n    }\n    return ans;\n}\n\n\n```\n```java []\npublic int maxCount(int[] banned, int n, int maxSum) {\n    Set<Integer> set = new HashSet<>(Arrays.asList(Arrays.stream(banned).boxed().toArray(Integer[]::new)));\n    int ans = 0;\n    for(int i = 1; i <= n; ++i){\n        if(!set.contains(i) && maxSum - i >= 0) { maxSum -= i; ans++; }\n    }\n    return ans;\n}\n```\n\n\n# Approach 2: O(1) space, O(NlogN) time\n\nHere we sort the banned array, and then iterate over i = 1.\nif i < banned[j], then consider it and increment the count.\nif i >= banned[j] then keep incrementing j until i < banned[j]\n\n```cpp []\nint maxCount(vector<int>& banned, int n, int maxSum) {\n    sort(banned.begin(), banned.end());\n    int ans = 0;\n    for(int i = 1, j = 0; i <= n; ++i){\n        if((j == banned.size() || i < banned[j] ) && maxSum- i >= 0) { \n            ans++; maxSum -= i; \n        }\n        while(j < banned.size() && i >= banned[j]) j++;\n    }\n    return ans;\n}\n```\n```java []\npublic int maxCount(int[] banned, int n, int maxSum) {\n    Arrays.sort(banned);\n    int ans = 0;\n    for(int i = 1, j = 0; i <= n; ++i){\n        if((j == banned.length || i < banned[j] ) && maxSum- i >= 0) { \n            ans++; maxSum -= i; \n        }\n        while(j < banned.length && i >= banned[j]) j++;\n    }\n    return ans;\n}\n```\n\n---\n\n\n<b>Here is an article of my recent interview experience at Amazon, you may like : \nhttps://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted\n\n---\n
['C++']