2529. Maximum Count of Positive Integer and Negative Integer

Problem Description

You are given an array nums that is sorted in non-decreasing order (smallest to largest). Your task is to count how many positive integers and how many negative integers are in the array, then return whichever count is larger.

Key points to understand:

The array is already sorted from smallest to largest
You need to count positive integers (numbers greater than 0)
You need to count negative integers (numbers less than 0)
The number 0 is neither positive nor negative, so don't count it
Return the maximum between these two counts

For example, if an array has 3 negative numbers and 5 positive numbers, you would return 5 since that's the larger count.

Since the array is sorted, we can use binary search to efficiently find the boundaries between negative numbers, zeros, and positive numbers. This gives us O(log n) time complexity instead of O(n) from a linear scan.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Since the array is sorted in non-decreasing order, all negative numbers appear first, followed by zeros (if any), and then positive numbers. This sorted structure means we can use binary search to find the boundaries efficiently.

We need to find two boundaries:

The first non-negative number (≥ 0): Everything before this index is negative, so negative_count = first_non_negative_index
The first positive number (> 0): Everything from this index onwards is positive, so positive_count = n - first_positive_index

For each boundary, we can frame the problem as finding the "first true" position in a boolean array:

For negative count: We search for the first index where nums[mid] >= 0 is true. The feasible function is nums[mid] >= 0.
For positive count: We search for the first index where nums[mid] > 0 is true. The feasible function is nums[mid] > 0.

Using the standard binary search template with first_true_index = -1, we can find these boundaries in O(log n) time. When first_true_index remains -1, it means no such element exists (e.g., all elements are negative for the first search).

Learn more about Binary Search patterns.

Solution Implementation

1class Solution:
2    def maximumCount(self, nums: List[int]) -> int:
3        """
4        Find the maximum count between positive and negative integers using binary search.
5
6        Args:
7            nums: A sorted list of integers in non-decreasing order
8
9        Returns:
10            The maximum count between positive and negative integers
11        """
12        n = len(nums)
13
14        # Binary search to find the first non-negative number (>= 0)
15        # Feasible condition: nums[mid] >= 0
16        left, right = 0, n - 1
17        first_non_negative = -1
18
19        while left <= right:
20            mid = (left + right) // 2
21            if nums[mid] >= 0:
22                first_non_negative = mid
23                right = mid - 1
24            else:
25                left = mid + 1
26
27        # Count of negative numbers
28        if first_non_negative == -1:
29            negative_count = n  # All elements are negative
30        else:
31            negative_count = first_non_negative
32
33        # Binary search to find the first positive number (> 0)
34        # Feasible condition: nums[mid] > 0
35        left, right = 0, n - 1
36        first_positive = -1
37
38        while left <= right:
39            mid = (left + right) // 2
40            if nums[mid] > 0:
41                first_positive = mid
42                right = mid - 1
43            else:
44                left = mid + 1
45
46        # Count of positive numbers
47        if first_positive == -1:
48            positive_count = 0  # No positive elements
49        else:
50            positive_count = n - first_positive
51
52        return max(negative_count, positive_count)
53

1class Solution {
2    /**
3     * Finds the maximum count between positive and negative numbers using binary search.
4     *
5     * @param nums the input sorted array of integers
6     * @return the maximum count between positive and negative numbers
7     */
8    public int maximumCount(int[] nums) {
9        int n = nums.length;
10
11        // Binary search to find the first non-negative number (>= 0)
12        // Feasible condition: nums[mid] >= 0
13        int left = 0;
14        int right = n - 1;
15        int firstNonNegative = -1;
16
17        while (left <= right) {
18            int mid = left + (right - left) / 2;
19            if (nums[mid] >= 0) {
20                firstNonNegative = mid;
21                right = mid - 1;
22            } else {
23                left = mid + 1;
24            }
25        }
26
27        // Count of negative numbers
28        int negativeCount;
29        if (firstNonNegative == -1) {
30            negativeCount = n;  // All elements are negative
31        } else {
32            negativeCount = firstNonNegative;
33        }
34
35        // Binary search to find the first positive number (> 0)
36        // Feasible condition: nums[mid] > 0
37        left = 0;
38        right = n - 1;
39        int firstPositive = -1;
40
41        while (left <= right) {
42            int mid = left + (right - left) / 2;
43            if (nums[mid] > 0) {
44                firstPositive = mid;
45                right = mid - 1;
46            } else {
47                left = mid + 1;
48            }
49        }
50
51        // Count of positive numbers
52        int positiveCount;
53        if (firstPositive == -1) {
54            positiveCount = 0;  // No positive elements
55        } else {
56            positiveCount = n - firstPositive;
57        }
58
59        return Math.max(negativeCount, positiveCount);
60    }
61}
62

1class Solution {
2public:
3    int maximumCount(vector<int>& nums) {
4        int n = nums.size();
5
6        // Binary search to find the first non-negative number (>= 0)
7        // Feasible condition: nums[mid] >= 0
8        int left = 0;
9        int right = n - 1;
10        int firstNonNegative = -1;
11
12        while (left <= right) {
13            int mid = left + (right - left) / 2;
14            if (nums[mid] >= 0) {
15                firstNonNegative = mid;
16                right = mid - 1;
17            } else {
18                left = mid + 1;
19            }
20        }
21
22        // Count of negative numbers
23        int negativeCount;
24        if (firstNonNegative == -1) {
25            negativeCount = n;  // All elements are negative
26        } else {
27            negativeCount = firstNonNegative;
28        }
29
30        // Binary search to find the first positive number (> 0)
31        // Feasible condition: nums[mid] > 0
32        left = 0;
33        right = n - 1;
34        int firstPositive = -1;
35
36        while (left <= right) {
37            int mid = left + (right - left) / 2;
38            if (nums[mid] > 0) {
39                firstPositive = mid;
40                right = mid - 1;
41            } else {
42                left = mid + 1;
43            }
44        }
45
46        // Count of positive numbers
47        int positiveCount;
48        if (firstPositive == -1) {
49            positiveCount = 0;  // No positive elements
50        } else {
51            positiveCount = n - firstPositive;
52        }
53
54        return max(negativeCount, positiveCount);
55    }
56};
57

1/**
2 * Finds the maximum count between positive and negative numbers using binary search
3 * @param nums - Sorted array of integers in non-decreasing order
4 * @returns The maximum count between positive numbers and negative numbers
5 */
6function maximumCount(nums: number[]): number {
7    const n = nums.length;
8
9    // Binary search to find the first non-negative number (>= 0)
10    // Feasible condition: nums[mid] >= 0
11    let left = 0;
12    let right = n - 1;
13    let firstNonNegative = -1;
14
15    while (left <= right) {
16        const mid = Math.floor((left + right) / 2);
17        if (nums[mid] >= 0) {
18            firstNonNegative = mid;
19            right = mid - 1;
20        } else {
21            left = mid + 1;
22        }
23    }
24
25    // Count of negative numbers
26    let negativeCount: number;
27    if (firstNonNegative === -1) {
28        negativeCount = n;  // All elements are negative
29    } else {
30        negativeCount = firstNonNegative;
31    }
32
33    // Binary search to find the first positive number (> 0)
34    // Feasible condition: nums[mid] > 0
35    left = 0;
36    right = n - 1;
37    let firstPositive = -1;
38
39    while (left <= right) {
40        const mid = Math.floor((left + right) / 2);
41        if (nums[mid] > 0) {
42            firstPositive = mid;
43            right = mid - 1;
44        } else {
45            left = mid + 1;
46        }
47    }
48
49    // Count of positive numbers
50    let positiveCount: number;
51    if (firstPositive === -1) {
52        positiveCount = 0;  // No positive elements
53    } else {
54        positiveCount = n - firstPositive;
55    }
56
57    return Math.max(negativeCount, positiveCount);
58}
59

Solution Approach

The solution uses binary search twice to find the boundaries between negative, zero, and positive numbers.

Binary Search Template: We use the standard template that finds the first index where a condition becomes true:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

Step 1: Find the First Non-Negative Number

Feasible condition: nums[mid] >= 0
This finds the first index where the element is ≥ 0
If first_true_index == -1, all elements are negative, so negative_count = n
Otherwise, negative_count = first_true_index (all elements before this are negative)

Step 2: Find the First Positive Number

Feasible condition: nums[mid] > 0
This finds the first index where the element is > 0
If first_true_index == -1, no positive elements exist, so positive_count = 0
Otherwise, positive_count = n - first_true_index (all elements from this index onward are positive)

Step 3: Return Maximum Return max(negative_count, positive_count).

Why This Works: In a sorted array, the feasible conditions create monotonic boolean patterns:

For nums[mid] >= 0: [false, false, ..., true, true, true] (all false until first non-negative)
For nums[mid] > 0: [false, false, ..., true, true, true] (all false until first positive)

The binary search efficiently finds where this transition from false to true occurs.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with the array nums = [-4, -1, 0, 0, 3, 5, 6] (n = 7):

Step 1: Find the First Non-Negative Number (feasible: nums[mid] >= 0)

Iteration	left	right	mid	nums[mid]	nums[mid] >= 0?	Action
Initial	0	6	-	-	-	first_true_index = -1
1	0	6	3	0	True	first_true_index = 3, right = 2
2	0	2	1	-1	False	left = 2
3	2	2	2	0	True	first_true_index = 2, right = 1
End	2	1	-	-	left > right	Exit loop

Result: first_true_index = 2, so negative_count = 2 (indices 0, 1 are negative: -4, -1)

Step 2: Find the First Positive Number (feasible: nums[mid] > 0)

Iteration	left	right	mid	nums[mid]	nums[mid] > 0?	Action
Initial	0	6	-	-	-	first_true_index = -1
1	0	6	3	0	False	left = 4
2	4	6	5	5	True	first_true_index = 5, right = 4
3	4	4	4	3	True	first_true_index = 4, right = 3
End	4	3	-	-	left > right	Exit loop

Result: first_true_index = 4, so positive_count = 7 - 4 = 3 (indices 4, 5, 6 are positive: 3, 5, 6)

Step 3: Return Maximum max(2, 3) = 3

The zeros at indices 2 and 3 are correctly excluded from both counts.

Time and Space Complexity

Time Complexity: O(log n)

The algorithm performs two binary searches, each taking O(log n) time. Each binary search halves the search space in every iteration until left > right. Since we perform a constant number (2) of binary searches, the total time complexity is O(log n) + O(log n) = O(log n).

This is a significant improvement over the O(n) linear scan approach, especially for large arrays.

Space Complexity: O(1)

The algorithm only uses a constant number of variables (left, right, mid, firstNonNegative, firstPositive, negativeCount, positiveCount), regardless of the input size. No additional data structures are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using Wrong Binary Search Template

The Problem: Using a different binary search variant like while left < right with right = mid instead of the standard template.

Why it matters: Different binary search templates have subtle differences in how they handle edge cases. Using an inconsistent template can lead to off-by-one errors or infinite loops.

Incorrect approach:

# Wrong template variant
left, right = 0, len(nums)
while left < right:
    mid = (left + right) // 2
    if nums[mid] >= 0:
        right = mid
    else:
        left = mid + 1
return left  # Directly returning left without tracking first_true_index

Correct approach (template-compliant):

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if nums[mid] >= 0:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

Pitfall 2: Confusing the Feasible Conditions

The Problem: Using the wrong condition for finding negative vs positive boundaries.

Common mistakes:

Using nums[mid] > 0 when looking for first non-negative (should be >= 0)
Using nums[mid] >= 0 when looking for first positive (should be > 0)

Remember:

First non-negative: nums[mid] >= 0 (includes zeros)
First positive: nums[mid] > 0 (excludes zeros)

Pitfall 3: Not Handling Edge Cases

The Problem: Not properly handling when first_true_index remains -1.

Edge cases to consider:

All elements are negative: first_non_negative == -1, so negative_count = n
All elements are positive: first_non_negative == 0 and first_positive == 0
All elements are zero: first_non_negative == 0 and first_positive == -1
No positive elements: first_positive == -1, so positive_count = 0

Solution: Always check if first_true_index == -1 before using it to calculate counts.

Pitfall 4: Counting Zeros Accidentally

The Problem: Incorrectly including zeros in either the negative or positive count.

Why it happens: Using >= 0 instead of > 0 for counting positives, or <= 0 instead of < 0 for counting negatives.

The Solution: Our binary search approach naturally handles this:

negative_count = first_non_negative counts elements strictly before the first non-negative (all negative)
positive_count = n - first_positive counts elements from first positive onward (all positive)
Zeros fall between these ranges and are correctly excluded

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know