Maximum Count of Positive Integer and Negative Integer - Video Solutions

Problem Overview: You receive a non-decreasing sorted integer array. The goal is simple: count how many values are negative and how many are positive, ignore zeros, and return whichever count is larger.

The sorted property of the array is the key detail. A straightforward solution scans the entire array and counts values. A more optimized approach uses binary search to directly locate the boundaries between negative numbers, zeros, and positive numbers.

Approach 1: Linear Scan (O(n) time, O(1) space)

The simplest approach is to iterate through the array once and maintain two counters: one for negative numbers and one for positive numbers. For each element, check if it is less than zero or greater than zero and increment the corresponding counter. Zeros are ignored because they are neither positive nor negative. After the traversal, return max(negativeCount, positiveCount). This approach works for any array regardless of sorting and is often the first solution you write in an interview to demonstrate basic correctness. The algorithm performs a single pass through the array, so the time complexity is O(n) and the space complexity is O(1).

Approach 2: Binary Search (O(log n) time, O(1) space)

Because the array is already sorted, you can use binary search to find boundaries instead of scanning the entire list. First find the index of the first element greater than zero (the first positive number). Then find the index of the first element greater than or equal to zero to determine where negative numbers stop. The number of negatives equals the index of the first non-negative element, and the number of positives equals n - firstPositiveIndex. These two searches run in O(log n) time and require constant extra space. This technique relies on efficient boundary detection rather than explicit iteration, which is a common pattern when solving counting problems on sorted arrays.

Recommended for interviews: Start with the linear scan to show correctness and clarity. Then mention the binary search optimization since the array is sorted. Interviewers typically expect you to recognize this property and reduce the runtime from O(n) to O(log n) using boundary searches.