Java Solution 🖥️ 4ms 💯Beats 91.11% 🏃🏼💨💨💨
Intuition\n Describe your first thoughts on how to solve this problem. \nWe want to find the largest positive integer k such that -k also exists in the array.\n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe want to find the largest positive integer `k` such that `-k` also exists in the array.\nNow there are two ways two search for such an integer `k`:\n\n# **Brute Force Method:**\n \nBrute force method is usually the simplest approach that we can come up for the solution and that is almost always doing exactly what the question asks. Since we want to find an integer `k` and its `additive inverse\xB9`, `-k` we can run two `for` loops to find such a number. We will run one `outer loop` to keep track of the maximum number at any particular instance and then run an `inner loop` to keep track of the `additive inverse\xB9` for the number at `i-th index`. This way we are keeping track of the maximum integer at every iteration and if its `additive inverse\xB9` exists in the array `nums` then we are storing it.\n  \n```java []\nN = nums.length;\nint max = Integer.MIN_VALUE;\nint ans = Integer.MIN_VALUE;\n\nfor (int i = 0; i < N; i++) {\n     max = Math.max(max, nums[i]) {\n\n     for (int j = 0; j < N; j++) {\n         int temp = nums[j] * -1;\n         if (temp == max) {\n             ans = Math.max(ans, max);\n        }\n    }\n}\n\nreturn ans;\n```\n\nThe **time complexity** of this approach is $$O(N^2)$$ as we iterate through the array eveytime for the number at `i-th index`. The Space Complexity is $$O(1)$$. Now the question arrises whether we can improve the efficiency of our code.\n\n**We can improve the Time Complexity with just two steps:**\n- Sorting The Array\n- Two Pointer Approach\n\n**Note:**\n\xB9 **Additive Inverse** of any integer is its negative counter part. Additive Inverse of `a` is `-a` and similarly additive inverse of `-a` is `a`. It is important to remember, to check whether two numbers are each other\'s `additve inverse\xB9`, we multiply one of them with `-1` instead of simply taking their absolute values. For example if `x = 1` and `y = 1`, then while their absolute values are equal, `x` and `y` are not each other\'s additive inverse.\n\n# Efficent Approach: Sorting with Two Pointers Approach\n<!-- Describe your approach to solving the problem. -->\n\nFirst we can sort the array and then take two pointers for the `first` and the `last` index.\n\n```\nArrays.sort(nums);\nint N = nums.length;\nint i = 0, j = N - 1;\n``` \n\nThen we run a while loop where we ensure that the `i-th` index is always smaller than the `j-th` index.\n\n```\nwhile (i < j) {\n    //Logic\n    //Some operations\n}\n```\n\nThen we access the values at the `i-th` and the `j-th` index and check if they are each other\'s `additive inverse\xB9` or not. If they are, then we can directly return the value at the `j-th index`. As we start from the last index of the sorted array and have found our `k-th` number, we do not need to go any further.\n\n    while (i < j) {\n        int start = nums[i];\n        int end = nums[j];\n\n        if ((start * -1) == end) {\n            return end;\n        } else if (/some other condition/) {\n                /Some other operation/\n        } else if (/another condition/) {\n            /another operation/\n        }\n    }\n\nIf, however, we have not found our `k-th` number, then we have to increment or decrement out pointers depending upon the result. If the number `additive inverse\xB9` of the `start` was greater than `end` then that means we have found a smaller negative number than we desire and we increment our `i-th index` to the right.\n\nHowever, if we found that `end` was greater than the `additive inverse` of `start` then that means the highest possiblity of `k-th` number is yet to be found and we move our `j-th index` to the left.\n\nIf, at last, we are unable to find any such `k-th` number we return `-1`\n\n# Complexity\n- Time complexity: $$O(N*log N + N)$$ `(Linearithmic TC)`\n$$(N * log N)$$ `(Logarithmic TC)`for sorting and $$O(N)$$ `(Linear TC)` for the two pointer approach. However, since `Linearithmic TC` has superseding value than `Linear TC` so over all $$O(N*log N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$ since there is no additional space used.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int findMaxK(int[] nums) {\n\n        Arrays.sort(nums);\n        int N = nums.length;\n        int i = 0, j = N - 1;\n\n        while (i < j) {\n            int start = nums[i];\n            int end = nums[j];\n\n            if ((start * -1) == end) {\n                return end;\n            } else if ((start * -1) < end) {\n                j--;\n            } else if ((start * -1) > end) {\n                i++;\n            }\n        }\n\n        return -1;\n    }\n}\n```
['Two Pointers', 'Sorting', 'Java']