Largest Positive Integer That Exists With Its Negative

Difficulty: Easy | Acceptance: 74.50% | Paid: No Topics: Array, Hash Table, Two Pointers, Sorting

Given an integer array nums, return the largest positive integer k such that -k also exists in the array. If there is no such integer, return -1.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Hash Set
• Approach 3: Sorting and Two Pointers

Examples

Input: nums = [-1,2,-3,3]
Output: 3
Explanation: 3 is the largest positive integer for which its negative -3 exists in the array.

Input: nums = [-1,10,6,7,-7,1]
Output: 7
Explanation: 7 is the largest positive integer for which its negative -7 exists in the array. Note that 10 is not a valid answer because -10 does not exist in the array.

Input: nums = [-10,8,6,7,-2,-3]
Output: -1
Explanation: There is no positive integer for which its negative exists in the array.

Constraints

1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000

Approach 1: Brute Force

Intuition We can iterate through every number in the array. For every positive number we encounter, we check if its negative counterpart exists anywhere else in the array.

Steps

• Initialize a variable max_k to -1.
• Iterate through the array with index i.
• If nums[i] is positive, iterate through the array again with index j.
• If nums[j] is equal to -nums[i], update max_k to the maximum of max_k and nums[i].
• Return max_k.

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        max_k = -1
        for i in range(len(nums)):
            if nums[i] > 0:
                for j in range(len(nums)):
                    if nums[j] == -nums[i]:
                        max_k = max(max_k, nums[i])
        return max_k

Complexity

• Time: O(n²) - We use nested loops to check every pair.
• Space: O(1) - We only use a constant amount of extra space.
• Notes: Simple to implement but inefficient for large inputs.

Approach 2: Hash Set

Intuition We can optimize the lookup process by storing all numbers in a Hash Set. This allows us to check for the existence of the negative counterpart in O(1) time.

Steps

• Initialize an empty Hash Set and a variable max_k to -1.
• Iterate through the array and add every number to the set.
• Iterate through the array again. If the current number n is positive and -n exists in the set, update max_k to the maximum of max_k and n.
• Return max_k.

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        seen = set(nums)
        max_k = -1
        for n in nums:
            if n > 0 and -n in seen:
                max_k = max(max_k, n)
        return max_k

Complexity

• Time: O(n) - We iterate through the array twice, and set operations are O(1) on average.
• Space: O(n) - In the worst case, we store all elements in the set.
• Notes: This is the most time-efficient approach for this problem.

Approach 3: Sorting and Two Pointers

Intuition If we sort the array, all negative numbers will be on the left and all positive numbers on the right. We can then use two pointers: one at the start (for negatives) and one at the end (for positives). We move the pointers towards each other to find a matching pair.

Steps

• Sort the array in ascending order.
• Initialize left pointer to 0 and right pointer to nums.length - 1.
• While left < right:
  • Calculate the absolute value of the negative number at left.
  • If abs(nums[left]) equals nums[right], we found a pair. Return nums[right] (which is the largest possible so far due to sorting).
  • If abs(nums[left]) is less than nums[right], the positive number is too large, so decrement right.
  • If abs(nums[left]) is greater than nums[right], the negative number is too small (in magnitude), so increment left.
• If the loop finishes without finding a pair, return -1.

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        while l < r:
            if -nums[l] == nums[r]:
                return nums[r]
            elif -nums[l] < nums[r]:
                r -= 1
            else:
                l += 1
        return -1

Complexity

• Time: O(n log n) - Sorting dominates the time complexity.
• Space: O(1) or O(n) - Depending on the sorting algorithm’s space complexity (e.g., O(log n) for quicksort, O(n) for merge sort).
• Notes: Useful if the array is already sorted or if space complexity is a strict constraint (though Hash Set is generally preferred for unsorted data).