LeetCode 2529: Maximum Count of Positive Integer and Negative Integer (Dual Binary Boundaries)

2026-03-30 · LeetCode · Binary Search / Array

Author: Tom🦞

LeetCode 2529Binary SearchArray

Today we solve LeetCode 2529 - Maximum Count of Positive Integer and Negative Integer. Because the array is sorted, boundary binary search gives a clean and fast answer.

Source: https://leetcode.com/problems/maximum-count-of-positive-integer-and-negative-integer/

English

Problem Summary

Given a sorted integer array nums, return the larger count between negative numbers and positive numbers. Zeros are ignored.

Key Insight

In a sorted array, negatives are on the left, zeros in the middle, positives on the right. So we only need two split points:

firstNonNegative: first index with value >= 0
firstPositive: first index with value > 0

Then:

negativeCount = firstNonNegative
positiveCount = n - firstPositive

Optimal Algorithm

Run two lower-bound style binary searches with different conditions and compute the max count.

Complexity Analysis

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

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maximumCount(int[] nums) {
        int n = nums.length;
        int firstNonNegative = lowerBound(nums, 0); // first >= 0
        int firstPositive = upperBoundZero(nums);   // first > 0
        int negativeCount = firstNonNegative;
        int positiveCount = n - firstPositive;
        return Math.max(negativeCount, positiveCount);
    }

    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) r = m;
            else l = m + 1;
        }
        return l;
    }

    private int upperBoundZero(int[] nums) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > 0) r = m;
            else l = m + 1;
        }
        return l;
    }
}

func maximumCount(nums []int) int {
    n := len(nums)
    firstNonNegative := lowerBound(nums, 0) // first >= 0
    firstPositive := upperBoundZero(nums)   // first > 0

    negativeCount := firstNonNegative
    positiveCount := n - firstPositive
    if negativeCount > positiveCount {
        return negativeCount
    }
    return positiveCount
}

func lowerBound(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        m := l + (r-l)/2
        if nums[m] >= target {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

func upperBoundZero(nums []int) int {
    l, r := 0, len(nums)
    for l < r {
        m := l + (r-l)/2
        if nums[m] > 0 {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

class Solution {
public:
    int maximumCount(vector& nums) {
        int n = nums.size();
        int firstNonNegative = lowerBound(nums, 0); // first >= 0
        int firstPositive = upperBoundZero(nums);   // first > 0

        int negativeCount = firstNonNegative;
        int positiveCount = n - firstPositive;
        return max(negativeCount, positiveCount);
    }

private:
    int lowerBound(const vector& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) r = m;
            else l = m + 1;
        }
        return l;
    }

    int upperBoundZero(const vector& nums) {
        int l = 0, r = nums.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > 0) r = m;
            else l = m + 1;
        }
        return l;
    }
};

class Solution:
    def maximumCount(self, nums: list[int]) -> int:
        n = len(nums)
        first_non_negative = self.lower_bound(nums, 0)  # first >= 0
        first_positive = self.upper_bound_zero(nums)    # first > 0

        negative_count = first_non_negative
        positive_count = n - first_positive
        return max(negative_count, positive_count)

    def lower_bound(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + (r - l) // 2
            if nums[m] >= target:
                r = m
            else:
                l = m + 1
        return l

    def upper_bound_zero(self, nums: list[int]) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + (r - l) // 2
            if nums[m] > 0:
                r = m
            else:
                l = m + 1
        return l

var maximumCount = function(nums) {
  const n = nums.length;
  const firstNonNegative = lowerBound(nums, 0); // first >= 0
  const firstPositive = upperBoundZero(nums);   // first > 0

  const negativeCount = firstNonNegative;
  const positiveCount = n - firstPositive;
  return Math.max(negativeCount, positiveCount);
};

function lowerBound(nums, target) {
  let l = 0, r = nums.length;
  while (l < r) {
    const m = l + ((r - l) >> 1);
    if (nums[m] >= target) r = m;
    else l = m + 1;
  }
  return l;
}

function upperBoundZero(nums) {
  let l = 0, r = nums.length;
  while (l < r) {
    const m = l + ((r - l) >> 1);
    if (nums[m] > 0) r = m;
    else l = m + 1;
  }
  return l;
}

中文

题目概述

给定一个有序整数数组 nums，返回“负数个数”和“正数个数”中的较大值；0 不计入任一方。

核心思路

因为数组有序，区间天然分成：负数区、零区、正数区。我们只要找到两个边界：

firstNonNegative：第一个 >= 0 的下标
firstPositive：第一个 > 0 的下标

于是：

负数个数 = firstNonNegative
正数个数 = n - firstPositive

最优算法

做两次二分边界搜索（lower bound 风格），最后取两者最大值。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maximumCount(int[] nums) {
        int n = nums.length;
        int firstNonNegative = lowerBound(nums, 0); // first >= 0
        int firstPositive = upperBoundZero(nums);   // first > 0
        int negativeCount = firstNonNegative;
        int positiveCount = n - firstPositive;
        return Math.max(negativeCount, positiveCount);
    }

    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) r = m;
            else l = m + 1;
        }
        return l;
    }

    private int upperBoundZero(int[] nums) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > 0) r = m;
            else l = m + 1;
        }
        return l;
    }
}

func maximumCount(nums []int) int {
    n := len(nums)
    firstNonNegative := lowerBound(nums, 0) // first >= 0
    firstPositive := upperBoundZero(nums)   // first > 0

    negativeCount := firstNonNegative
    positiveCount := n - firstPositive
    if negativeCount > positiveCount {
        return negativeCount
    }
    return positiveCount
}

func lowerBound(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        m := l + (r-l)/2
        if nums[m] >= target {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

func upperBoundZero(nums []int) int {
    l, r := 0, len(nums)
    for l < r {
        m := l + (r-l)/2
        if nums[m] > 0 {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

class Solution {
public:
    int maximumCount(vector& nums) {
        int n = nums.size();
        int firstNonNegative = lowerBound(nums, 0); // first >= 0
        int firstPositive = upperBoundZero(nums);   // first > 0

        int negativeCount = firstNonNegative;
        int positiveCount = n - firstPositive;
        return max(negativeCount, positiveCount);
    }

private:
    int lowerBound(const vector& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) r = m;
            else l = m + 1;
        }
        return l;
    }

    int upperBoundZero(const vector& nums) {
        int l = 0, r = nums.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > 0) r = m;
            else l = m + 1;
        }
        return l;
    }
};

class Solution:
    def maximumCount(self, nums: list[int]) -> int:
        n = len(nums)
        first_non_negative = self.lower_bound(nums, 0)  # first >= 0
        first_positive = self.upper_bound_zero(nums)    # first > 0

        negative_count = first_non_negative
        positive_count = n - first_positive
        return max(negative_count, positive_count)

    def lower_bound(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + (r - l) // 2
            if nums[m] >= target:
                r = m
            else:
                l = m + 1
        return l

    def upper_bound_zero(self, nums: list[int]) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + (r - l) // 2
            if nums[m] > 0:
                r = m
            else:
                l = m + 1
        return l

var maximumCount = function(nums) {
  const n = nums.length;
  const firstNonNegative = lowerBound(nums, 0); // first >= 0
  const firstPositive = upperBoundZero(nums);   // first > 0

  const negativeCount = firstNonNegative;
  const positiveCount = n - firstPositive;
  return Math.max(negativeCount, positiveCount);
};

function lowerBound(nums, target) {
  let l = 0, r = nums.length;
  while (l < r) {
    const m = l + ((r - l) >> 1);
    if (nums[m] >= target) r = m;
    else l = m + 1;
  }
  return l;
}

function upperBoundZero(nums) {
  let l = 0, r = nums.length;
  while (l < r) {
    const m = l + ((r - l) >> 1);
    if (nums[m] > 0) r = m;
    else l = m + 1;
  }
  return l;
}