Maximum Count of Positive Integer and Negative Integer

easy binary search array counting

Problem

Given an array nums sorted in non-decreasing order, let pos be the number of positive integers and neg be the number of negative integers. Return the maximum of pos and neg. Note that 0 is neither positive nor negative.

Inputnums = [-2,-1,-1,1,2,3]

Output3

There are 3 positive integers and 3 negative integers. The maximum count is 3.

Inputnums = [-3,-2,-1,0,0,1,2]

Output3

There are 2 positives and 3 negatives. The two zeros count for neither side.

nums (sorted, comma-separated)

def maximum_count(nums):
    # first index with nums[i] >= 0  -> that many negatives
    neg = lower_bound(nums, 0)
    # first index with nums[i] >= 1  -> rest are positives
    pos = len(nums) - lower_bound(nums, 1)
    return max(neg, pos)

def lower_bound(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

function maximumCount(nums) {
  // first index with nums[i] >= 0 -> that many negatives
  const neg = lowerBound(nums, 0);
  // first index with nums[i] >= 1 -> rest are positives
  const pos = nums.length - lowerBound(nums, 1);
  return Math.max(neg, pos);
}

function lowerBound(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

int maximumCount(int[] nums) {
    // first index with nums[i] >= 0 -> that many negatives
    int neg = lowerBound(nums, 0);
    // first index with nums[i] >= 1 -> rest are positives
    int pos = nums.length - lowerBound(nums, 1);
    return Math.max(neg, pos);
}

int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int maximumCount(vector<int>& nums) {
    // first index with nums[i] >= 0 -> that many negatives
    int neg = lowerBound(nums, 0);
    // first index with nums[i] >= 1 -> rest are positives
    int pos = (int)nums.size() - lowerBound(nums, 1);
    return max(neg, pos);
}

int lowerBound(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Explanation

Because nums is already sorted, all negatives sit on the left, all positives sit on the right, and any zeros form a block in the middle. So we only need to find two boundaries, and we can find them with binary search instead of scanning the whole array.

The workhorse is lowerBound(nums, target): it returns the first index i where nums[i] >= target. Equivalently, it returns how many elements are strictly less than target.

Negatives: the count of values strictly less than 0 is exactly lowerBound(nums, 0) — the first index that is not negative. Everything before it is negative.

Positives: the first index whose value is at least 1 is lowerBound(nums, 1). Every element from there to the end is positive, so pos = n - lowerBound(nums, 1). The zeros (values that are >= 0 but < 1) fall between the two boundaries and are counted by neither.

Each binary search narrows a half-open window [lo, hi): if the middle value is below the target we move lo right, otherwise we pull hi in. The loop ends when lo == hi, which is the boundary index. Two such searches give the answer in O(log n) time.

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