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.
This approach improves upon the brute-force method by first sorting the array. Once sorted, we can use a two-pointer technique to efficiently find pairs of numbers that sum to zero.
Algorithm
1. Sort the input array `nums` in ascending order.2. Initialize two pointers, `left = 0` and `right = nums.length - 1`.3. Loop while `left < right`.4. Calculate `sum = nums[left] + nums[right]`.5. If `sum == 0`, a pair is found. The positive value is `nums[right]`. We have found a candidate for `k`, so we can return `nums[right]` as the largest possible `k` because we started from the largest positive number.6. If `sum < 0`, it means `nums[left]` is too small in magnitude. Move the left pointer to the right to increase the sum: `left++`.7. If `sum > 0`, it means `nums[right]` is too large. Move the right pointer to the left to decrease the sum: `right--`.8. If the loop finishes without finding a pair where the sum is zero, it means no such `k` exists, so return -1.import java.util.Arrays; class Solution { public int findMaxK(int[] nums) { Arrays.sort(nums); int left = 0; int right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == 0) { // Since the array is sorted, nums[right] is the largest k found so far. // Because we are moving from the ends, this is the largest possible k. return nums[right]; } else if (sum < 0) { left++; } else { // sum > 0 right--; } } return -1; }}Walkthrough
First, the input array nums is sorted in ascending order. Then, two pointers are initialized: left at the beginning of the array and right at the end. The algorithm proceeds by checking the sum of the values at these two pointers, nums[left] + nums[right].
- If the sum is zero, it means
nums[left]is the negative ofnums[right]. Since the array is sorted and we are starting from the largest positive number (nums[right]), this must be the largestkthat satisfies the condition, so we can return it immediately. - If the sum is less than zero, we need a larger sum, so we increment the
leftpointer to consider a larger (less negative) number. - If the sum is greater than zero, we need a smaller sum, so we decrement the
rightpointer to consider a smaller positive number. This process continues until the pointers cross each other. If no pair is found, the loop completes and we return -1.
Complexity
Time
O(n log n), where n is the number of elements. The dominant operation is sorting the array. The subsequent two-pointer scan takes O(n) time.
Space
O(log n) to O(n), depending on the implementation of the sorting algorithm used. For example, `Arrays.sort()` in Java for primitives uses a variant of Quicksort, which has an average space complexity of O(log n) for the recursion stack. In the worst case, it can be O(n).
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
The two-pointer technique is a common and useful pattern for problems on sorted arrays.
Cons
The cost of sorting can be significant for very large datasets.
It modifies the original array, which might not be desirable. Creating a copy would require O(n) space.
This is the most time-efficient approach. It uses a hash set to keep track of the numbers encountered so far. This allows for checking the existence of a number's negative counterpart in constant average time.
Algorithm
1. Initialize an empty `HashSet<Integer>` called `seen`.2. Initialize a variable `maxK = -1`.3. Iterate through each number `num` in the `nums` array.4. Check if the set `seen` contains the negative counterpart, `-num`.5. If it does, a pair is found. Update `maxK = Math.max(maxK, Math.abs(num))`.6. Add the current `num` to the `seen` set regardless of whether a pair was found.7. After the loop finishes, return `maxK`.import java.util.HashSet;import java.util.Set; class Solution { public int findMaxK(int[] nums) { Set<Integer> seen = new HashSet<>(); int maxK = -1; for (int num : nums) { if (seen.contains(-num)) { maxK = Math.max(maxK, Math.abs(num)); } seen.add(num); } return maxK; }}Walkthrough
The algorithm iterates through the input array nums just once. It uses a HashSet to store numbers it has seen. For each number num in the array, it checks if the negative of that number, -num, is already present in the hash set. If it is, a pair (k, -k) has been found, where k is the absolute value of num. We then update our result, maxK, with the maximum k found so far. After the check, the current number num is added to the hash set for future lookups. This single pass ensures that we find all possible pairs and correctly identify the largest k.
Complexity
Time
O(n), where n is the number of elements in the array. We iterate through the array once, and each hash set operation (insertion and lookup) takes O(1) time on average.
Space
O(n) in the worst case. This occurs when all elements in the input array are unique, and the hash set needs to store all of them.
Trade-offs
Pros
Optimal time complexity, making it very fast for large inputs.
Relatively simple to implement and understand.
Cons
Requires extra space proportional to the number of unique elements in the array.
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; }}class Solution {public: int findMaxK(vector<int> &nums) { unordered_set<int> s(nums.begin(), nums.end()); int ans = -1; for (int x : s) { if (s.count(-x)) { ans = max(ans, x); } } return ans; }};class Solution: def findMaxK(self, nums: List[int]) -> int: s = set(nums) return max((x for x in s if - x in s), default=- 1)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.