Problem Description

You are given an integer array nums that contains no zeros. Your task is to find the largest positive integer k where both k and -k exist in the array.

The problem asks you to identify pairs of opposite numbers (positive and negative) in the array and return the largest positive value among these pairs. If no such pair exists, return -1.

For example:

• If nums = [3, -3, 1, -1, 4], both 3 and -3 exist, and both 1 and -1 exist. The largest positive value is 3, so return 3.
• If nums = [1, 2, 3, 4], there are no negative counterparts for any positive numbers, so return -1.
• If nums = [-1, -2, -3, 3], only 3 and -3 form a valid pair, so return 3.

The solution uses a hash table approach by converting the array to a set for O(1) lookup time. It then checks each element x in the set to see if its negative counterpart -x also exists. Among all valid pairs, it returns the maximum positive value, or -1 if no such pairs exist.

Intuition

The key insight is that we need to find pairs of numbers that are opposites of each other (like 3 and -3). When looking for such pairs, a natural question arises: how can we efficiently check if the negative counterpart of a number exists in the array?

A brute force approach would involve checking every element against every other element, which would take O(n²) time. However, we can optimize this by recognizing that we just need to answer a yes/no question: "Does -x exist in the array for a given x?"

This type of membership checking is perfectly suited for a hash table (or set in Python), which provides O(1) lookup time. By first converting our array into a set, we can quickly check if any element's negative counterpart exists.

Once we have this efficient lookup structure, we can iterate through all elements and check if their negative counterparts exist. Since we want the largest positive integer k, we need to track the maximum value among all valid pairs.

The elegant part of the solution is using Python's generator expression with max() function: max((x for x in s if -x in s), default=-1). This automatically:

1. Filters for only those elements x where -x also exists in the set
2. Finds the maximum among these valid elements
3. Returns -1 if no such pairs exist (using the default parameter)

This approach ensures we examine each element only once while maintaining optimal time complexity of O(n).

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution uses a hash table-based approach to efficiently find the largest positive integer that has its negative counterpart in the array.

Step 1: Create a Hash Set

s = set(nums)

We convert the input array nums into a set s. This transformation serves two purposes:

• Removes any duplicate values (though duplicates don't affect our answer)
• Enables O(1) time complexity for checking if an element exists

Step 2: Find Maximum Valid Pair

return max((x for x in s if -x in s), default=-1)

This line does the heavy lifting through a generator expression:

• for x in s: Iterate through each unique element in the set
• if -x in s: Check if the negative counterpart of x exists in the set
• This generates all elements that have their opposite number in the array
• max(...): Find the maximum value among these valid elements
• default=-1: If no valid pairs exist (empty generator), return -1

Why This Works:

• When we check if -x in s, we're identifying both positive and negative numbers that form valid pairs
• For example, if we have 3 and -3 in the set:
  • When x = 3, we check if -3 exists (it does)
  • When x = -3, we check if 3 exists (it does)
• The max() function naturally returns the largest value, which will always be positive among valid pairs (since for any pair (k, -k), the positive k is larger than -k)

Time Complexity: O(n) where n is the length of the array

• Converting array to set: O(n)
• Iterating through set and checking membership: O(n)

Space Complexity: O(n) for storing the set

Example Walkthrough

Let's walk through the solution with nums = [-2, 5, -3, 2, 3, -5].

Step 1: Create a Hash Set

s = set([-2, 5, -3, 2, 3, -5])
# s = {-2, 5, -3, 2, 3, -5}

We convert the array into a set for O(1) lookup operations.

Step 2: Check Each Element for Its Negative Counterpart

Let's trace through the generator expression (x for x in s if -x in s):

• x = -2: Check if -(-2) = 2 is in set → YES ✓ (2 exists)
• x = 5: Check if -5 is in set → YES ✓ (-5 exists)
• x = -3: Check if -(-3) = 3 is in set → YES ✓ (3 exists)
• x = 2: Check if -2 is in set → YES ✓ (-2 exists)
• x = 3: Check if -3 is in set → YES ✓ (-3 exists)
• x = -5: Check if -(-5) = 5 is in set → YES ✓ (5 exists)

The generator produces: -2, 5, -3, 2, 3, -5

Step 3: Find Maximum

max([-2, 5, -3, 2, 3, -5]) = 5

The function returns 5, which is indeed the largest positive integer that has its negative counterpart in the array.

Verification: We can see that the valid pairs are:

• (2, -2) → largest positive is 2
• (3, -3) → largest positive is 3
• (5, -5) → largest positive is 5

Among these, 5 is the maximum, confirming our answer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs the following operations:

• Converting the list nums to a set: O(n) where n is the length of the array
• The generator expression (x for x in s if -x in s) iterates through each element in the set once: O(n) iterations
• For each element x, checking if -x in s is O(1) on average for set lookup
• The max() function processes all elements from the generator: O(n)

Overall time complexity: O(n) + O(n) = O(n)

Space Complexity: O(n)

The algorithm uses:

• A set s to store all unique elements from nums: O(n) in the worst case when all elements are unique
• The generator expression creates an iterator but doesn't store all values at once, using O(1) additional space
• The max() function uses O(1) space to track the maximum value

Overall space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Filtering Only Positive Numbers

The Mistake: A common error is to only check positive numbers when looking for pairs, thinking that we only need to verify if their negative counterparts exist:

# INCORRECT approach
def findMaxK(self, nums: List[int]) -> int:
    num_set = set(nums)
    # Only checking positive numbers
    positive_nums = [num for num in num_set if num > 0]
    for num in sorted(positive_nums, reverse=True):
        if -num in num_set:
            return num
    return -1

Why It's Wrong: While this might seem logical since we want the "largest positive k", it adds unnecessary complexity and filtering. The original solution's beauty is that it checks ALL numbers (both positive and negative), and max() naturally returns the positive value from each valid pair.

The Fix: Trust the max() function to handle both positive and negative values correctly. When both k and -k exist, max() will always select k (the positive one) over -k.

Pitfall 2: Not Handling Edge Cases Properly

The Mistake: Forgetting to handle the case when no valid pairs exist, leading to a ValueError:

# INCORRECT - will raise ValueError on empty sequence
def findMaxK(self, nums: List[int]) -> int:
    num_set = set(nums)
    return max(num for num in num_set if -num in num_set)  # Missing default parameter

Why It's Wrong: When no valid pairs exist (e.g., nums = [1, 2, 3]), the generator expression produces an empty sequence, causing max() to raise a ValueError: max() arg is an empty sequence.

The Fix: Always include the default=-1 parameter in the max() function to handle empty sequences gracefully:

return max((num for num in num_set if -num in num_set), default=-1)

Pitfall 3: Using List Comprehension Instead of Generator Expression

The Mistake: Using a list comprehension when a generator expression would be more efficient:

# Less efficient approach
def findMaxK(self, nums: List[int]) -> int:
    num_set = set(nums)
    # Creates entire list in memory
    valid_pairs = [num for num in num_set if -num in num_set]
    return max(valid_pairs) if valid_pairs else -1

Why It's Suboptimal: While this works correctly, it creates an entire list in memory containing all valid numbers before finding the maximum. This uses extra space unnecessarily.

The Fix: Use a generator expression (with parentheses) instead of a list comprehension (with square brackets). The generator expression is more memory-efficient as it yields values one at a time:

return max((num for num in num_set if -num in num_set), default=-1)