Largest Positive Integer That Exists With Its Negative

easy two pointers sorting array

Problem

Given an integer array nums that contains no zeros, find the largest positive integer k such that -k also appears in the array. Return that k, or -1 if no such integer exists.

Inputnums = [-1, 10, 6, 7, -7, 1]

Output7

Both 1 and 7 have their negatives present; 7 is the larger valid k.

Inputnums = [-10, 8, 6, 7, -2, -3]

Output-1

No value has its negation also in the array, so the answer is -1.

nums (comma-separated, no zeros)

def find_max_k(nums):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == 0:
            return nums[hi]
        elif s < 0:
            lo += 1
        else:
            hi -= 1
    return -1

function findMaxK(nums) {
  nums.sort((a, b) => a - b);
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const s = nums[lo] + nums[hi];
    if (s === 0) {
      return nums[hi];
    } else if (s < 0) {
      lo++;
    } else {
      hi--;
    }
  }
  return -1;
}

int findMaxK(int[] nums) {
    Arrays.sort(nums);
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int s = nums[lo] + nums[hi];
        if (s == 0) {
            return nums[hi];
        } else if (s < 0) {
            lo++;
        } else {
            hi--;
        }
    }
    return -1;
}

int findMaxK(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int s = nums[lo] + nums[hi];
        if (s == 0) {
            return nums[hi];
        } else if (s < 0) {
            lo++;
        } else {
            hi--;
        }
    }
    return -1;
}

Explanation

We want the largest k where both k and -k live in the array. A pair (a, b) with a < 0 < b is a valid match exactly when a + b == 0, and then k = b.

After sorting the array ascending, the most negative numbers sit on the left and the most positive on the right. We place pointer lo at the left end and hi at the right end and look at the sum nums[lo] + nums[hi].

If the sum is 0, we've found a matching pair. Because hi currently points at the largest value not yet ruled out, the very first zero-sum we hit gives the largest possible k, so we return nums[hi] immediately.

If the sum is negative, the left value is "too negative" to pair with the current right value, so we move lo rightward to a less negative number. If the sum is positive, the right value is too large, so we move hi leftward. Each comparison discards one element, so the scan is linear after the sort.

If the pointers meet without ever summing to zero, no valid pair exists and we return -1. Example: [-1,10,6,7,-7,1] sorts to [-7,-1,1,6,7,10]; the pointers slide inward until -7 + 7 = 0, yielding k = 7.

Time: O(n log n) Space: O(1)