LeetCode 2441 - Largest Positive Integer That Exists With Its Negative

LeetCode Problem 2441

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers, Sorting

Solution

Problem Understanding

The problem asks us to find the largest positive integer k in a given array nums such that its negative counterpart -k also exists in the array. In other words, for each positive integer in the array, we need to check whether its negative exists. If multiple positive integers satisfy this property, we return the largest one. If none exist, we return -1.

The input array contains integers in the range [-1000, 1000] and explicitly excludes zero. The array length can be up to 1000, which is small enough to allow straightforward solutions, but we can optimize further. The constraints guarantee that there are no zeros, so we do not need to handle zero as a special case. Important edge cases include arrays where all integers are positive, all are negative, or where positive/negative pairs exist but only for smaller values.

Approaches

The brute-force approach involves checking every positive integer in the array and seeing if its negative exists. This guarantees correctness because it explicitly verifies each possible candidate, but it is inefficient because for each element we may have to scan the entire array, resulting in O(n²) time complexity.

A more optimal approach leverages a hash set. By storing all numbers in a set, we can check for the existence of -num in constant time for each positive integer num. We then track the maximum positive integer that satisfies this condition. This reduces the time complexity to O(n) while using O(n) additional space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every positive number against the rest of the array for its negative
Optimal	O(n)	O(n)	Use a hash set for O(1) lookup of negative values

Algorithm Walkthrough

1. Initialize an empty set num_set to store all integers from the input array. This allows O(1) membership checks.
2. Iterate through the array and add each number to num_set. This ensures we can efficiently check for the negative of any number.
3. Initialize a variable max_k to -1. This will store the largest positive integer whose negative exists.
4. Iterate through the array again. For each number num, check if num is positive and if -num exists in num_set.
5. If both conditions are satisfied, update max_k to be the maximum of max_k and num.
6. After processing all numbers, return max_k.

Why it works: The algorithm maintains the invariant that max_k always stores the largest positive integer found so far that has a corresponding negative in the array. By checking all numbers exactly once and using a set for quick negative lookup, we guarantee correctness in O(n) time.

Python Solution

from typing import List

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

In this implementation, we first populate a set num_set to allow constant-time lookups. We then iterate through the numbers, checking for positive values that have their negative counterpart in the set. We update max_k only if a larger valid number is found. Finally, max_k is returned, either containing the largest valid integer or -1 if none exists.

Go Solution

func findMaxK(nums []int) int {
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }

    maxK := -1
    for _, num := range nums {
        if num > 0 {
            if _, exists := numSet[-num]; exists {
                if num > maxK {
                    maxK = num
                }
            }
        }
    }
    return maxK
}

The Go implementation mirrors the Python solution. We use a map numSet for O(1) lookups. The logic for checking positive numbers and updating maxK remains identical. Go requires explicit handling of map existence checks using the _, exists := map[key] syntax.

Worked Examples

Example 1: nums = [-1,2,-3,3]

Step	num_set	max_k	Check
Init	{}	-1	-
Add numbers	{-1,2,-3,3}	-1	-
Check -1	-	-1	num < 0, skip
Check 2	-	-1	-2 not in set, skip
Check -3	-	-1	num < 0, skip
Check 3	-	3	-3 exists, update max_k

Output: 3

Example 2: nums = [-1,10,6,7,-7,1]

Step	num_set	max_k	Check
Init	{}	-1	-
Add numbers	{-1,10,6,7,-7,1}	-1	-
Check numbers	1 → -1 exists, max_k = 1; 10 → -10 not exist; 6 → -6 not exist; 7 → -7 exists, max_k = 7	max_k = 7

Output: 7

Example 3: nums = [-10,8,6,7,-2,-3]

No positive integer has its negative in the array. Output: -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to build set and one pass to check positives
Space	O(n)	Store all numbers in a hash set

The time complexity is linear since we only iterate over the array twice and set operations are O(1). Space complexity is linear because we store each element in the set.

Test Cases

# Provided examples
assert Solution().findMaxK([-1,2,-3,3]) == 3  # Only 3 has negative counterpart
assert Solution().findMaxK([-1,10,6,7,-7,1]) == 7  # 1 and 7 valid, 7 is largest
assert Solution().findMaxK([-10,8,6,7,-2,-3]) == -1  # No valid k

# Edge cases
assert Solution().findMaxK([1,-1]) == 1  # Smallest valid array
assert Solution().findMaxK([1000,-1000,500,-500]) == 1000  # Largest numbers in range
assert Solution().findMaxK([5,4,3,2,1]) == -1  # Only positives, no negatives
assert Solution().findMaxK([-5,-4,-3,-2,-1]) == -1  # Only negatives, no positives
assert Solution().findMaxK([2,-1,1,-2,3,-3]) == 3  # Multiple pairs, largest returned

Test	Why
[-1,2,-3,3]	Single valid k check
[-1,10,6,7,-7,1]	Multiple valid positives, pick largest
[-10,8,6,7,-2,-3]	No valid k, return -1
[1,-1]	Minimum size array
[1000,-1000,500,-500]	Maximum values in range
[5,4,3,2,1]	Positives only, no negative counterpart
[-5,-4,-3,-2,-1]	Negatives only, no positive counterpart
[2,-1,1,-2,3,-3]	Multiple pairs, ensure max is selected

Edge Cases

The first edge case is arrays with all positive or all negative numbers. A naive implementation may incorrectly assume a valid k exists, but our algorithm correctly returns -1 because the negative counterpart is missing.

The second edge case involves duplicate numbers. For example, [1,1,-1,-1] still yields 1 because duplicates do not affect the maximum positive integer search. The hash set naturally handles duplicates.

The third edge case is numbers at the extremes of the allowed range, such as [-1000,1000]. Our solution correctly identifies 1000 as the largest valid integer since it can handle any integer in the range without overflow.