#2529

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Count of Positive Integer and Negative Integer

Compute the maximum count between positive and negative integers in a sorted array using efficient binary search counting.

array binary search counting

Problem Statement

You are given an integer array nums sorted in non-decreasing order. Your task is to determine the maximum count between the number of positive integers and the number of negative integers. Note that zeros do not contribute to either count.

Return a single integer representing the larger count between positive and negative numbers in the array. For example, given nums = [-2,-1,-1,1,2,3], there are 3 positive and 3 negative integers, so the output is 3.

Examples

Example 1

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

Output: 3

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

Example 2

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

Output: 3

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

Example 3

Input: nums = [5,20,66,1314]

Output: 4

There are 4 positive integers and 0 negative integers. The maximum count among them is 4.

Constraints

1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums is sorted in a non-decreasing order.

Solution Approach

Count Positive Integers via Binary Search

Perform a binary search to locate the first positive number in the sorted array. Subtract its index from the total length to get the count of positive integers.

Count Negative Integers via Binary Search

Use binary search to find the last negative number in the array. The index of this element plus one gives the count of negative integers.

Compare and Return Maximum Count

After obtaining counts of positive and negative integers, return the larger of the two. This step ensures the solution adheres to the problem requirement of maximizing the count.

Complexity Analysis

Metric	Value
Time	O(\log N)
Space	O(1)

Time complexity is O(log N) due to two binary searches, each over the sorted array. Space complexity is O(1) because no extra data structures are used, only counters and pointers.

What Interviewers Usually Probe

Check if the candidate correctly identifies zeros as neutral and ignores them in counts.
Listen for a binary search approach instead of linear counting to assess efficiency.
Confirm if the solution correctly handles arrays with all positives or all negatives.

Common Pitfalls or Variants

Common pitfalls

Counting zeros as positive or negative, which skews the result.
Using linear scan instead of binary search, leading to O(N) time complexity.
Off-by-one errors when computing counts from indices after binary search.

Follow-up variants

Find maximum counts in a rotated sorted array with the same positive/negative rule.
Return both counts of positive and negative integers instead of the maximum.
Handle unsorted arrays by sorting first, then applying the binary search counting approach.

FAQ

What does 'Maximum Count of Positive Integer and Negative Integer' ask for?

It asks for the largest number of positive or negative integers in a sorted array, ignoring zeros.

Can I solve this problem without binary search?

Yes, a linear scan works but binary search reduces time complexity from O(N) to O(log N).

How should zeros be treated?

Zeros are neutral and must not be counted as either positive or negative numbers.

What if all numbers are positive or all negative?

The maximum count is simply the total number of elements in the array for the present sign.

Is binary search required for this problem pattern?

Binary search is optimal since the array is sorted, enabling O(log N) counting of positives and negatives.

terminal

Solution

Solution 1: Traversal

We can directly traverse the array, count the number of positive and negative integers $a$ and $b$, and return the larger of $a$ and $b$.

1

2

3

4

5

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        a = sum(x > 0 for x in nums)
        b = sum(x < 0 for x in nums)
        return max(a, b)

Solution 2: Binary Search

Since the array is sorted in non-decreasing order, we can use binary search to find the index $i$ of the first element that is greater than or equal to $1$, and the index $j$ of the first element that is greater than or equal to $0$. The number of positive integers is $a = n - i$, and the number of negative integers is $b = j$. We return the larger of $a$ and $b$.

1

2

3

4

5

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        a = sum(x > 0 for x in nums)
        b = sum(x < 0 for x in nums)
        return max(a, b)

Continue Practicing

#2856 minimum array length after pair removals #3186 maximum total damage with spell casting #1782 count pairs of nodes