Problem Informations

• Problem Index: 2529
• Problem Link: Maximum Count of Positive Integer and Negative Integer
• Topics: Array, Binary Search, Counting

Problem Description

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.

Example 1:

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:

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:

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 \leq \text{nums.length} \leq 2000$
• $-2000 \leq \text{nums}[i] \leq 2000$
• nums is sorted in a non-decreasing order.

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

Intuition

The problem requires us to determine the maximum count between positive and negative integers in a sorted array. Given that the list is sorted in non-decreasing order, the positive integers will be located after any negative integers and zeros. This allows us to efficiently use binary search-based algorithms to identify the boundaries between negative and positive integers. By locating the first positive and the last negative integers, we can calculate their respective counts and return the highest of the two.

Approach

To tackle this problem, we leverage the properties of a sorted array in conjunction with binary search techniques. The main steps are as follows:

1. Count Positive Integers: Use upper_bound to find the first element greater than 0. The number of positive integers is the distance from this iterator to the end of the array. upper_bound efficiently uses a binary search approach to find this boundary in $O(\log(n))$ time.

2. Count Negative Integers: Utilize lower_bound to locate the first element not less than 0, effectively identifying the boundary between negative numbers and zero/positive numbers. The count of negative integers can be ascertained by calculating the distance from the array’s beginning to this boundary. Similar to upper_bound, lower_bound operates in $O(\log(n))$ time.

3. Determine Maximum Count: With both counts obtained, simply return the maximum value between the number of positive and negative integers using the max function.

Given that the array is sorted, these steps ensure an efficient solution due to the use of logarithmic search techniques, thereby adhering to the problem’s constraints and complexities.

Code

C++

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        // Calculate the number of positive integers.
        // upper_bound returns an iterator pointing to the first element greater than 0.
        int positiveCount = nums.end() - upper_bound(nums.begin(), nums.end(), 0);

        // Calculate the number of negative integers.
        // lower_bound returns an iterator pointing to the first element not less than 0.
        int negativeCount = lower_bound(nums.begin(), nums.end(), 0) - nums.begin();

        // Return the maximum count between positive and negative integers.
        return max(positiveCount, negativeCount);
    }
};

Python

class Solution:
    def maximumCount(self, nums):
        # Calculate the number of positive integers.
        # bisect_right returns the index of the first element greater than 0.
        positiveCount = len(nums) - bisect.bisect_right(nums, 0)

        # Calculate the number of negative integers.
        # bisect_left returns the index of the first element not less than 0.
        negativeCount = bisect.bisect_left(nums, 0)

        # Return the maximum count between positive and negative integers.
        return max(positiveCount, negativeCount)

Complexity

• Time complexity: The time complexity of the solution is $O(\log n)$. This complexity arises from the use of upper_bound and lower_bound functions. Both functions utilize binary search, as they are part of the C++ Standard Library’s algorithms for sorted ranges, and therefore operate in $O(\log n)$ time complexity.

• Space complexity: The space complexity of the solution is $O(1)$. The algorithm uses a constant amount of extra space for storing integer variables such as positiveCount and negativeCount. Hence, no additional space is required that scales with the size of the input nums.