Problem Statement

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k. If there is no such integer, return -1.

Examples

Example 1:

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the only valid k we can find in the array.

Example 2:

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: Both 1 and 7 have their corresponding negative values in the array. 7 has a larger value.

Example 3:

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no a single valid k, we return -1.

Constraints

• 1 <= nums.length <= 1000

• -1000 <= nums[i] <= 1000

• nums[i] != 0

Intuition

Whenever you com across a problem in DSA, after reading the question. The first thought you should have is, Which data-structure can I use to solve this problem? If no data-structure seems to fit, then Which algorithm or approach can be used to solve the problem? Following the same thought process, lets see:

Which data-structure could be used?

In the question, we want to find the highest same number (+ve, -ve) pair. One thing that we can do is to memorize all the +ve or -ve numbers in the given array. Once we have memorized that, we can simply find the max number whose (+ve, -ve) pair is present in the array.

The best data-structure to do this will be a Dictionary/HashMap/HashTable/Map.

Which algorithm/approach could be used?

If we use a data-structure then we generally increase our space complexity. So, it's good to think of an optimization if possible using an algorithm/approach which avoids using that data-structure. Although, this doesn't always mean that the algorithmic approach is better as it might be slower due to high Time complexity.

So, solving DSA problems is a delicate between handling time and space complexity.

In this question, if we sort the array in ascending order. Then we can iterate the array in reverse, while checking if a matching -ve number exist in the array. We return as soon as we find such a value.

Code Solution

Python code:

• Using Dictionary:

class Solution:
    # TC: O(n)
    # SC: O(n)
    def findMaxK(self, nums: List[int]) -> int:
        # initialize the dictionary
        elem_map=dict()
        # initialize the ans variable to -inf
        ans=-float('inf')
        # store all possible numbers in the dictionary
        for num in nums:
            if num>0:
                elem_map[num]=True
        # find highest same number (+ve,-ve) pair
        for num in nums:
            # for every -ve number check 
            # if there's a +ve number in the dictionary
            if num<0:
                # if +ve number exist then check if it is
                # greater then current highest
                # else return -inf
                if elem_map.get(-num,-float('inf'))!=-float('inf'):
                    if -num>ans:
                        ans=-num
        # if ans is -inf that means we have not found the pair                        
        if ans==-float('inf'):
            ans=-1        
        return ans

• Using Sorting:

class Solution:
    # TC: O(nlogn)
    # SC: O(1)
    def findMaxK(self, nums: List[int]) -> int:
        # sort input array in ascending order
        nums.sort()
        # iterate in reverse so that we check the highest number
        for index in range(len(nums)-1,-1,-1):
            # check if the highest +ve number has a corresponding -ve
            if nums[index]>0 and -nums[index] in nums:
                # return if a pair exist
                return nums[index]
        # if no pair found then return -1
        return -1

Time and Space complexity

Time Complexity:

• Using Dictionary

$$O(n)$$

We iterate over the input array at most once.

• Using Sorting

$$O(n\ logn)$$

Since we use sorting.

Space complexity:

• Using Dictionary

$$O(n)$$

Since we use a dictionary, in the worst case we will use the same space as the input array.

• Using Sorting

$$O(1)$$

This is because we don't utilize any more space in our solution.

Conclusion

This array question is quite straightforward. You can tackle it by:

• Using a dictionary

• Using sorting

Hope that explanation made sense and you found this blog helpful. If you've made it this far, please give it a like and drop a comment.

Happy Coding!🚀