Largest Positive Integer That Exists With Its Negative
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a straightforward, brute-force method with nested loops. It iterates through every possible pair of numbers in the array to check if one is the negative of the other.
Algorithm
1. Initialize a variable `maxK = -1` to store the largest `k` found.2. Iterate through the array with an outer loop from `i = 0` to `n-1`.3. Inside the outer loop, iterate through the array with an inner loop from `j = 0` to `n-1`.4. In the inner loop, check if `nums[i]` is the negative of `nums[j]` (i.e., `nums[i] == -nums[j]`).5. If the condition is met, it means we found a pair. Update `maxK` with the positive value of this pair: `maxK = Math.max(maxK, Math.abs(nums[i]))`.6. After the loops complete, return `maxK`.class Solution { public int findMaxK(int[] nums) { int maxK = -1; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) { if (nums[i] == -nums[j]) { maxK = Math.max(maxK, Math.abs(nums[i])); } } } return maxK; }}Walkthrough
The algorithm initializes a variable maxK to -1. It then uses two nested loops to compare every element nums[i] with every other element nums[j]. If a pair (nums[i], nums[j]) is found such that nums[j] == -nums[i], it means we've found a number and its negative. We then take the positive value of this pair, which is abs(nums[i]), and update maxK if this value is larger than the current maxK. After checking all pairs, the final maxK is returned. If no such pair is found, maxK remains -1.
Complexity
Time
O(n^2), where n is the number of elements in the `nums` array. This is because for each element, we scan the entire array again, leading to a quadratic number of comparisons.
Space
O(1), as we only use a constant amount of extra space for variables like `maxK`.
Trade-offs
Pros
Very simple to conceptualize and implement.
Requires no additional data structures, resulting in constant space complexity.
Cons
Highly inefficient for larger arrays due to its quadratic time complexity.
Performs many redundant checks.
Solutions
Solution
class Solution {public int findMaxK(int[] nums) { int ans = -1; Set<Integer> s = new HashSet<>(); for (int x : nums) { s.add(x); } for (int x : s) { if (s.contains(-x)) { ans = Math.max(ans, x); } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.