Largest Positive Integer That Exists With Its Negative - Solution & Explanation
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.
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] <= 1000nums[i] != 0
Approach Overview
Problem Overview: You are given an integer array nums. The task is to find the largest positive integer k such that both k and -k appear in the array. If no such integer exists, return -1. The goal is to efficiently detect matching positive–negative pairs and track the maximum valid value.
Approach 1: Using HashSet for Fast Lookup (O(n) time, O(n) space)
This approach relies on a hash set for constant‑time lookups. First iterate through the array and insert each number into a HashSet. Then iterate again and check whether the opposite value (-num) exists in the set. Whenever both numbers exist, update the answer with the maximum positive value encountered. Because each lookup is O(1) on average, the full scan takes O(n) time while storing elements requires O(n) space. This is the most direct solution using a Hash Table and works well for unsorted input arrays.
Approach 2: Sorting to Simplify Pair Search (O(n log n) time, O(1) extra space)
Sorting the array groups negative and positive numbers in order, which makes it easier to find matching pairs. After sorting, use two pointers: one starting from the left (most negative) and one from the right (largest positive). Compare the absolute values of the numbers. If they match, you found a valid pair and can return that positive number immediately. If the absolute value on the left is larger, move the left pointer forward; otherwise move the right pointer backward. Sorting costs O(n log n), and the two‑pointer scan runs in O(n) time with O(1) additional space. This method combines Sorting with the Two Pointers technique.
Recommended for interviews: The hash set approach is typically expected because it achieves optimal O(n) time and is straightforward to implement. Interviewers want to see that you recognize the symmetric relationship between k and -k and use constant‑time lookups to detect pairs efficiently. The sorting approach is still valuable because it demonstrates comfort with pointer techniques and problem transformation, but it is slightly less optimal due to the sorting step.
Approach 1: Using HashSet for Fast Lookup
This approach utilizes a HashSet to keep track of the numbers we have encountered. As we iterate through the list, we check both the presence of a number and its negative in the HashSet. We update the largest number that satisfies the condition.
The approach uses an integer array as a hash set to track numbers from -1000 to 1000. We check for each number if its opposite exists in the hash set. If it does, we see if it forms the largest valid integer.
Complexity
Time Complexity: O(n), since we iterate through the array once.
Space Complexity: O(1), since the hash set array size is always constant and independent of input size.
Approach 2: Sorting to Simplify Pair Search
In this approach, we first sort the array so that we can efficiently find pairs of positive and negative numbers. Once sorted, we use two pointers: one starting from the beginning (for negative numbers) and one from the end (for positive numbers) to find the largest integer pair where both a positive and its negative exist.
This approach sorts the array to facilitate efficient pair searching through two pointers. By manipulating two indices moving inwards, we detect equal absolute pairs and subsequently update the largest value.
Complexity
Time Complexity: O(n log n) for the sorting operation.
Space Complexity: O(1) additional space beyond input storing.
Approach 3: Hash Table
We can use a hash table s to record all elements that appear in the array, and a variable ans to record the maximum positive integer that satisfies the problem requirements, initially ans = -1.
Next, we traverse each element x in the hash table s. If -x exists in s, then we update ans = max(ans, x).
After the traversal ends, return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Approach 4: Default Approach
Code
Rust
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using HashSet for Fast Lookup | Time Complexity: O(n), since we iterate through the array once. |
| Sorting to Simplify Pair Search | Time Complexity: O(n log n) for the sorting operation. |
| Hash Table | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Fast Lookup | O(n) | O(n) | Best general solution when the array is unsorted and fast membership checks are needed |
| Sorting + Two Pointers | O(n log n) | O(1) | Useful when sorting is acceptable or when practicing two-pointer techniques |
Video Solution
2441. Largest Positive Integer That Exists With Its Negative | Leetcode Weekly 315 | LeetCode 2441 • Bro Coders • 1,706 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Largest Positive Integer That Exists With Its Negative easy or hard?
Largest Positive Integer That Exists With Its Negative Python/Java solution
How to solve Largest Positive Integer That Exists With Its Negative in O(n)?
What is the best approach for Largest Positive Integer That Exists With Its Negative?
Is Largest Positive Integer That Exists With Its Negative asked at Google/Amazon/Meta?
What data structure is used in Largest Positive Integer That Exists With Its Negative?
What is the time complexity of Largest Positive Integer That Exists With Its Negative?
Ready to solve this problem?
Practice Largest Positive Integer That Exists With Its Negative with our built-in code editor and test cases.
Practice on FleetCode