Problem

Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.

  • In other words, if the number of positive integers in nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.

Note that 0 is neither positive nor negative.

Examples

Example 1:

1
2
3
4
5
6
7


    
    
    Input: nums = [-2,-1,-1,1,2,3]
    Output: 3
    Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.

Example 2:

1
2
3
4
5
6
7


    
    
    Input: nums = [-3,-2,-1,0,0,1,2]
    Output: 3
    Explanation: There are 2 positive integers and 3 negative integers. The maximum count among them is 3.

Example 3:

1
2
3
4
5
6
7


    
    
    Input: nums = [5,20,66,1314]
    Output: 4
    Explanation: 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.

Follow up: Can you solve the problem in O(log(n)) time complexity?

Solution

We need to calculate the count of positive and negative integers in a sorted array (nums) and return the maximum between the two. It is essential to note that nums is sorted in non-decreasing order, which allows us to use binary search or simple traversal for efficiency.

Method 1 - Binary Search

Approach

  1. Identify Negatives: Using the sorted property of the array, the negative numbers will always appear at the start, followed by zero (if present), and then the positive numbers.
  2. Binary Search for Transition Points:
    • To count negative numbers (neg), find the index of the first non-negative number (≥ 0).
    • For positive numbers (pos), find the index of the first positive number (> 0).
  3. Calculate Counts: Subtract indices or use list slicing to count negative and positive numbers.
  4. Return Result: Compute the maximum of neg and pos.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public int maximumCount(int[] nums) {
        int n = nums.length;
        int negCount = 0, posCount = 0;

        // Find the first non-negative index (all before are negatives)
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < 0) {
                negCount = mid + 1;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // Find the first positive index (all after are positives)
        left = 0; right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > 0) {
                posCount = n - mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // Return the maximum of negative and positive counts
        return Math.max(negCount, posCount);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        n: int = len(nums)
        neg_count: int = 0
        pos_count: int = 0

        # Find the first non-negative index
        left: int = 0
        right: int = n - 1
        while left <= right:
            mid: int = left + (right - left) // 2
            if nums[mid] < 0:
                neg_count = mid + 1
                left = mid + 1
            else:
                right = mid - 1

        # Find the first positive index
        left = 0
        right = n - 1
        while left <= right:
            mid: int = left + (right - left) // 2
            if nums[mid] > 0:
                pos_count = n - mid
                right = mid - 1
            else:
                left = mid + 1

        # Return the maximum of negative and positive counts
        return max(neg_count, pos_count)

Complexity

  • ⏰ Time complexity:  O(log n) for binary search to find the transition points in the worst case.
  • 🧺 Space complexity: O(1) since no additional data structures are used.

Dry Run

1

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

Execution:

  • Negative count = 3 (indices 0–2).
  • Positive count = 3 (indices 4–6).
  • Output = 3.