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] != 0This 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) for the sorting operation.
Space Complexity: O(1) additional space beyond input storing.
| 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. |
2441. Largest Positive Integer That Exists With Its Negative | 5 Ways | 2 Pointers | Bitset • Aryan Mittal • 1,400 views views
Watch 9 more video solutions →Practice Largest Positive Integer That Exists With Its Negative with our built-in code editor and test cases.
Practice on FleetCode