3 solutions | O(n^2), O(n logn) and O(n) | ✅
\n---\n\n# BRUTEFORCE SOLUTION (O(N^2))\n\n---\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nA brute force approach involves c
\n---\n\n# BRUTEFORCE SOLUTION $$(O(N^2))$$\n\n---\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nA brute force approach involves checking every pair of elements in the array to see if their absolute values are equal. This requires nested loops to compare each element with every other element.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use nested loops to iterate through each pair of elements in the array.\n2. For each pair, check if the absolute values are equal.\n3. If a pair with equal absolute values is found, update the maximum positive integer `k`.\n4. After checking all pairs, return the maximum positive integer `k` found. If no such pair is found, return `-1`.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`O(n^2)`, where `n` is the size of the input array. This is because we have nested loops to check each pair of elements.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`O(1)` since we\'re using constant extra space.\n\n# Code\n```\nclass Solution {\npublic:\n    int findMaxK(vector<int>& nums) {\n        int maxK = -1;\n        for (int i = 0; i < nums.size(); ++i) {\n            for (int j = i + 1; j < nums.size(); ++j) {\n                if (abs(nums[i]) == nums[j]) {\n                    maxK = max(maxK, nums[i]);\n                }\n            }\n        }\n        return maxK;\n    }\n};\n\n```\n\n\n---\n\n# SORTING SOLUTION $$(O(N LOG N))$$\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find the largest positive integer `k` such that its negative exists in the given array, we can sort the array and then traverse it from both ends. By doing so, we ensure that we consider both positive and negative numbers. We compare the absolute values of the numbers at the `start` and `end` of the array. If they are equal, we return that value as k. If the absolute value at the `start` is less than the absolute value at the `end`, we move the `end` pointer inward. Otherwise, we move the `start` pointer inward. If we exhaust the array without finding such a pair, we return `-1`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort the array to simplify the search process.\n2. Initialize two pointers, one at the `start` and one at the `end`` of the array.\n3. Traverse the array from both ends:\n- If the absolute value at the `start` equals the value at the `end`, return that value as `k`.\n- If the absolute value at the `start` is less than the value at the `end`, move the `end` pointer inward.\n- If the absolute value at the `start` is greater than the value at the `end`, move the `start` pointer inward.\n4. If no such pair is found, return `-1`.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`O(nlogn)` due to the sorting step, where `n` is the size of the input array.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`O(1)` since we\'re using constant extra space.\n\n# Code\n```\nclass Solution {\npublic:\n    int findMaxK(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        int start = 0;\n        int end = nums.size()-1;\n        while(start < end && nums[start] < 0 && nums[end] > 0){\n            if(abs(nums[start]) == nums[end]) \n                return nums[end];\n            else if(abs(nums[start]) < nums[end]) \n                end--;\n            else\n                start++;\n        }\n        return -1;\n    }\n};\n```\n---\n\n# UNORDERED SET SOLUTION $$(O(n))$$\n\n---\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve the problem in linear time complexity `O(n)`, we can utilize a hash set to efficiently check for the existence of negative counterparts for each positive integer in the array. By iterating through the array once, we can determine the largest positive integer k such that its negative counterpart exists in the array.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize an `unordered set` to store the numbers encountered in the array.\n2. Iterate through the array once.\n3. For each element in the array:\n- Check if it is a positive integer and if its negative counterpart exists in the set.\n- If both conditions are met, update the maximum positive integer \n`k` found so far.\n- After iterating through the array, return the maximum positive integer \n`k` found. \n4. If no such pair is found, return `-1`.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`O(n)`, where `n` is the size of the input array. This is because we iterate through the array once.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`O(n)` due to the hash set used to store the numbers encountered in the array.\n# Code\n```\nclass Solution {\npublic:\n    int findMaxK(vector<int>& nums) {\n        unordered_set<int> numSet(nums.begin(), nums.end());\n        int maxK = -1;\n        for (int num : nums) {\n            if (num > 0 && numSet.count(-num)) {\n                maxK = max(maxK, num);\n            }\n        }\n        return maxK;\n    }\n};\n```\n\n---\n\n\n\n
['Two Pointers', 'Sorting', 'C++']