C++ || 6 different approaches || clean code
The leetcode runtimes are not very consistent, but approach 3 seems to be the fastest.\n\n### Approach 1: brute force (127ms)\n\nThe problem is constraint enoug
The leetcode runtimes are not very consistent, but approach 3 seems to be the fastest.\n\n### Approach 1: brute force (127ms)\n\nThe problem is constraint enough that we can just use brute force.\n\n```cpp\n    static int findMaxK(const vector<int>& nums) {\n        int ans = -1;\n        for (int i : nums)\n            for (int j : nums)\n                if (i == -j) ans = max(ans, abs(i));\n\n        return ans;\n    }\n```\n\n**Complexity Analysis**\n  * Time complexity: $$O(n^2)$$\n  * Space complexity: $$O(1)$$\n\n### Approach 2: hash set, two passes (42ms)\n\nIn the first pass we keep track of all the negative numbers in a hash set and in the next pass we look at all to positive numbers.\n\n```cpp\n    static int findMaxK(const vector<int>& nums) {\n        unordered_set<int> neg;\n        for (int num : nums) {\n            if (num < 0) neg.insert(num);\n        }\n        int ans = -1;\n        for (int num : nums) {\n            if (num > ans && neg.count(-num)) ans = num;\n        }\n        return ans;\n    }\n```\n\n**Complexity Analysis**\n  * Time complexity: $$O(n)$$\n  * Space complexity: $$O(n)$$\n\n### Approach 3: bitset, two passes (7ms)\n\nThe input range is limited enough that we can just use a ```bitset```.\n\n```cpp\n    static int findMaxK(const vector<int>& nums) {\n        bitset<1024> neg;\n        for (int num : nums) {\n            if (num < 0) neg[-num] = true;\n        }\n        int ans = -1;\n        for (int num : nums) {\n            if (num > ans && neg[num]) ans = num;\n        }\n        return ans;\n    }\n```\n\n**Complexity Analysis**\n  * Time complexity: $$O(n)$$\n  * Space complexity: $$O(1)$$ albeit it\'s a big 1.\n\n### Approach 4: hash set, single pass (36ms)\n\nIf we keep track of both negative and positive numbers we can also solve the problem in a single pass.\n\n```cpp\n    static int findMaxK(const vector<int>& nums) {\n        int ans = 0;\n        unordered_set<int> seen;\n        for (int num : nums) {\n            const int abs_num = abs(num);\n            if (abs_num > ans && seen.count(-num)) ans = abs_num;\n            seen.insert(num);\n        }\n        return ans ?: -1;\n    }\n```\n\nThe complexity is the same as approach 2.\n\n### Approach 5: bitset, single pass (29ms)\n\nAgain, we can just use a ```bitset```.\n\n```cpp\n    static int findMaxK(const vector<int>& nums) {\n        int ans = 0;\n        bitset<2048> seen;\n        for (int num : nums) {\n            const int abs_num = abs(num);\n            if (abs_num > ans && seen[-num + 1024]) ans = abs_num;\n            seen[num + 1024] = true;\n        }\n        return ans ?: -1;\n    }\n```\n\nThe complexity is the same as approach 3.\n\n### Approach 6: sort and two pointers\n\nThis is a variation of a solution for the two sum problem, but we have to sort the input first. Note that all the other approach don\'t modify ```nums```.\n\n```cpp\n    static int findMaxK(vector<int>& nums) {\n        sort(begin(nums), end(nums));\n        int lo = 0;\n        int hi = size(nums) - 1;\n        while (lo < hi) {\n            if (-nums[lo] == nums[hi]) {\n                return nums[hi];\n            } else if (-nums[lo] > nums[hi]) {\n                ++lo;\n            } else {\n                --hi;\n            }\n        }\n        return -1;\n    }\n```\n\n**Complexity Analysis**\n  * Time complexity: $$O(n \\log n)$$ for the ```std::sort```ing the rest is linear.\n  * Space complexity: $$O(\\log n)$$ for the quicksort part of ```std::sort```.\n\n_As always: Feedback, questions, and comments are welcome. Leaving an upvote sparks  joy! :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**\n
['Two Pointers', 'C', 'Sorting', 'C++']