LeetCode Problem 2529

Difficulty: 🟢 Easy
Topics: Array, Binary Search, Counting

Solution

LeetCode 2529 - Maximum Count of Positive Integer and Negative Integer

Problem Understanding

The problem gives us a sorted integer array nums in non-decreasing order. Our task is to count how many numbers are positive and how many numbers are negative, then return the larger of the two counts.

A positive integer is any value greater than 0, while a negative integer is any value less than 0. The value 0 itself is neither positive nor negative, so it should not contribute to either count.

For example, in the array [-2, -1, -1, 1, 2, 3], there are three negative values and three positive values. Since both counts are equal, the answer is 3.

The important detail is that the array is already sorted. This property allows us to do more than simply scan every element. Because all negative values appear before zeros, and all zeros appear before positive values, we can use binary search to efficiently locate the boundaries between these regions.

The constraints are relatively small:

• 1 <= nums.length <= 2000
• -2000 <= nums[i] <= 2000

Even a linear scan would easily pass within these limits. However, the follow up asks whether we can solve the problem in O(log n) time, which strongly suggests using binary search.

Several edge cases are important:

• Arrays containing only positive numbers
• Arrays containing only negative numbers
• Arrays containing only zeros
• Arrays with multiple zeros in the middle
• Arrays where positive and negative counts are equal
• Arrays of length 1

A naive implementation can easily make mistakes by counting zeros incorrectly or by mishandling boundary indices during binary search.

Approaches

Brute Force Approach

The simplest solution is to iterate through the array once and maintain two counters:

• negative_count
• positive_count

For each number:

• If the number is less than 0, increment the negative counter.
• If the number is greater than 0, increment the positive counter.
• Ignore zeros.

At the end, return the larger of the two counters.

This approach is straightforward and guaranteed to be correct because every element is examined exactly once. However, it does not take advantage of the fact that the array is already sorted.

Optimal Approach Using Binary Search

Because the array is sorted, all negative values form a contiguous block at the beginning, and all positive values form a contiguous block at the end.

This means we can use binary search to locate:

• The first index containing 0 or a positive number
• The first index containing a positive number

From these positions:

• The number of negatives equals the index of the first non-negative value.
• The number of positives equals n - first_positive_index.

This avoids scanning the entire array and achieves O(log n) time complexity.

The key observation is that sorted order allows boundary searching instead of element-by-element counting.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scans every element and counts positives and negatives
Optimal	O(log n)	O(1)	Uses binary search to find region boundaries

Algorithm Walkthrough

Optimal Binary Search Algorithm

1. Compute the length of the array n.
2. Use binary search to find the first index where the value is greater than or equal to 0.

This index represents the start of the non-negative region. Since all negative numbers appear before this point, the number of negatives equals this index. 3. Store this value as negative_count. 4. Use another binary search to find the first index where the value is strictly greater than 0.

This index represents the start of the positive region. 5. Compute the number of positives as:

positive_count = n - first_positive_index

6. Return the maximum of negative_count and positive_count.

Why it works

The algorithm relies on the sorted property of the array. Since all negative numbers appear before zeros and positives, the first non-negative position exactly separates negatives from everything else. Similarly, the first positive position separates zeros from positives.

Binary search correctly identifies these boundaries in logarithmic time, and the counts derived from these indices are therefore accurate.

Python Solution

from bisect import bisect_left, bisect_right
from typing import List

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        negative_count = bisect_left(nums, 0)
        positive_count = len(nums) - bisect_right(nums, 0)

        return max(negative_count, positive_count)

The implementation uses Python's built in bisect module, which provides efficient binary search utilities.

bisect_left(nums, 0) returns the first index where 0 could be inserted while maintaining sorted order. This is exactly the position of the first non-negative number, which also equals the number of negative numbers.

bisect_right(nums, 0) returns the first index after all zeros. Every element after this position is positive, so the number of positive elements is len(nums) - bisect_right(nums, 0).

Finally, the solution returns the larger of the two counts.

Go Solution

import "sort"

func maximumCount(nums []int) int {
	n := len(nums)

	negativeCount := sort.Search(n, func(i int) bool {
		return nums[i] >= 0
	})

	firstPositive := sort.Search(n, func(i int) bool {
		return nums[i] > 0
	})

	positiveCount := n - firstPositive

	if negativeCount > positiveCount {
		return negativeCount
	}

	return positiveCount
}

The Go solution uses sort.Search, which performs binary search over indices.

The first search finds the first index where nums[i] >= 0, which determines the negative count.

The second search finds the first index where nums[i] > 0, which determines where positive numbers begin.

Unlike Python, Go does not provide direct equivalents of bisect_left and bisect_right, so we express the search conditions manually using anonymous functions.

Worked Examples

Example 1

Input:

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

Step 1: Find first non-negative element

Index	Value
0	-2
1	-1
2	-1
3	1

The first value greater than or equal to 0 would be inserted at index 3.

So:

negative_count = 3

Step 2: Find first positive element

The first positive number is also at index 3.

So:

positive_count = 6 - 3 = 3

Step 3: Return maximum

max(3, 3) = 3

Final answer:

3

Example 2

Input:

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

Step 1: Find first non-negative element

Index	Value
0	-3
1	-2
2	-1
3	0

The first non-negative value is at index 3.

So:

negative_count = 3

Step 2: Find first positive element

Index	Value
5	1

The first positive value is at index 5.

So:

positive_count = 7 - 5 = 2

Step 3: Return maximum

max(3, 2) = 3

Final answer:

3

Example 3

Input:

nums = [5, 20, 66, 1314]

Step 1: Find first non-negative element

The first non-negative value is already at index 0.

So:

negative_count = 0

Step 2: Find first positive element

The first positive value is also at index 0.

So:

positive_count = 4 - 0 = 4

Step 3: Return maximum

max(0, 4) = 4

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Two binary searches are performed
Space	O(1)	Only a few variables are used

Each binary search halves the search space repeatedly, resulting in logarithmic time complexity. Since only constant extra memory is used regardless of input size, the space complexity is constant.

Test Cases

sol = Solution()

assert sol.maximumCount([-2, -1, -1, 1, 2, 3]) == 3  # equal positives and negatives
assert sol.maximumCount([-3, -2, -1, 0, 0, 1, 2]) == 3  # zeros in the middle
assert sol.maximumCount([5, 20, 66, 1314]) == 4  # all positive
assert sol.maximumCount([-5, -4, -3]) == 3  # all negative
assert sol.maximumCount([0, 0, 0]) == 0  # only zeros
assert sol.maximumCount([-1, 0, 1]) == 1  # balanced around zero
assert sol.maximumCount([1]) == 1  # single positive element
assert sol.maximumCount([-1]) == 1  # single negative element
assert sol.maximumCount([0]) == 0  # single zero
assert sol.maximumCount([-2, -1, 0, 0, 0]) == 2  # negatives larger
assert sol.maximumCount([0, 0, 1, 2, 3, 4]) == 4  # positives larger
assert sol.maximumCount([-10, -5, -1, 0, 2]) == 3  # mixed values

Test Summary

Test	Why
[-2, -1, -1, 1, 2, 3]	Validates equal counts
[-3, -2, -1, 0, 0, 1, 2]	Ensures zeros are ignored
[5, 20, 66, 1314]	Tests all positive numbers
[-5, -4, -3]	Tests all negative numbers
[0, 0, 0]	Tests all zeros
[-1, 0, 1]	Small balanced input
[1]	Single positive value
[-1]	Single negative value
[0]	Single zero
[-2, -1, 0, 0, 0]	More negatives than positives
[0, 0, 1, 2, 3, 4]	More positives than negatives
[-10, -5, -1, 0, 2]	Mixed values with one positive

Edge Cases

Arrays Containing Only Zeros

An array like [0, 0, 0] can cause incorrect counting if zeros are mistakenly treated as positive or negative. The implementation avoids this by specifically searching for values greater than 0 when counting positives and values less than 0 when counting negatives. As a result, both counts correctly become 0.

Arrays With No Positive Numbers

Consider [-5, -4, -1]. In this case, the binary search for the first positive value returns the array length. The positive count becomes:

n - n = 0

This correctly indicates that there are no positive numbers.

Arrays With No Negative Numbers

For an array like [1, 2, 3], the first non-negative index is 0, meaning the negative count is 0. The first positive index is also 0, so the positive count becomes the entire array length. This ensures the implementation correctly handles arrays composed entirely of positive values.

Multiple Zeros Between Negative and Positive Regions

Arrays such as [-3, -2, 0, 0, 0, 5, 6] are especially important because zeros form a middle section that should not affect either count. The use of two separate binary searches guarantees that zeros are excluded from both totals.