2441

2441. Largest Positive Integer That Exists With Its Negative (Easy)

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

Companies: Microsoft

Related Topics:
Array, Hash Table, Two Pointers, Sorting

Similar Questions:

• Two Sum (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/largest-positive-integer-that-exists-with-its-negative
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int findMaxK(vector<int>& A) {
        sort(begin(A), end(A));
        for (int i = 0, j = A.size() - 1; i < j && A[i] < 0 && A[j] > 0;) {
            if (-A[i] == A[j]) return A[j];
            if (-A[i] > A[j]) ++i;
            else --j;
        }
        return -1;
    }
};

We can have O(N) time O(D) space with counting sort.