Largest Positive Integer That Exists With Its Negative

We need to find the largest positive integer k in the list such that -k is also in the list. If there is no such integer, we need to return -1.

The key to solve this problem is to make use of a set data structure. We will follow these steps:

  1. Initialize a variable max_k to -1, which will store the maximum positive k found so far.
  2. Initialize an empty set named num_set to store the numbers.
  3. Iterate over each number in nums.
    • If the negative of the current number is in num_set and the absolute value of current number is greater than max_k, update max_k with the absolute value of the current number.
    • Add the current number to num_set.
  4. After the loop, return max_k.

Here is the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        max_k = -1
        num_set = set()

        for num in nums:
            if -num in num_set:
                max_k = max(max_k, abs(num))
            num_set.add(num)

        return max_k

This algorithm works because it checks for each number in nums if its negation is in the set. If it is, it checks if the absolute value of this number is the largest found so far. In the end, it will return the largest k if found, or -1 if not. The time complexity of this solution is O(n), where n is the length of the nums list. The space complexity is also O(n), for storing the numbers in a set.