# Largest Positive Integer That Exists With Its Negative
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-positive-integer-that-exists-with-its-negative)
Canonical: https://scaleengineer.com/dsa/problems/largest-positive-integer-that-exists-with-its-negative
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## 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`.

**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`

# Approaches
## Brute Force with Nested Loops
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.
**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`.
**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.
### Explanation
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.
### Algorithm
```markdown
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`.
```
```java
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;
    }
}
```

## Sorting with Two Pointers
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.
**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).
**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.
### Explanation
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 of `nums[right]`. Since the array is sorted and we are starting from the largest positive number (`nums[right]`), this must be the largest `k` that 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 `left` pointer to consider a larger (less negative) number.
- If the sum is greater than zero, we need a smaller sum, so we decrement the `right` pointer 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.
### Algorithm
```markdown
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.
```
```java
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;
    }
}
```

## Single-Pass with a Hash Set
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.
**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.
**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.
### Explanation
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`.
### Algorithm
```markdown
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`.
```
```java
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;
    }
}
```

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```