2441. Largest Positive Integer That Exists With Its Negative
Description
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] <= 1000
nums[i] != 0
Solutions
Solution 1: 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.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Solution 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|