Largest Positive Integer That Exists With Its Negative

Problem

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.

Examples

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.

Solution

Refer the video for detailed solution.

Method 1 - Naive

This problem is similar to 2sum problem. We can use brute force or naive approach - where we can run nested loop, for each number in outer loop, we search for the negative number in inner loop. If we find, update the max pointer. Time complexity is O(n^2)

Method 2 - Sorting

Another approach is Sorting. Sort the array, and start iterating from right, till we find the negative number. As, our output is positive number. Search for negative of the number in the array, and if we find, that is the answer. Time complexity for sorting is O(n log n), and then we iterate on array, which takes O(n) time, and each binary search takes O(log n), hence overall time complexity is O(n log n).

Method 3 - Hashing

We can iterate on array, and add elements to hashset, and search for negative number of the array element. If we find one, we will update the max value accordingly. We use hashset, as the time complexity there is O(1).

Code

Java

public int findMaxK(int[] nums) {
	Set<Integer> set = new HashSet<>();
	int max = -1;
	for (int num: nums) {
		set.add(num);
		int neg = -1 * num;
		if (set.contains(neg)) {
			max = Math.max(max, Math.abs(num));
		}
	}
	return max;
}