Maximum Count of Positive Integer and Negative Integer

Difficulty: Easy | Acceptance: 74.30% | Paid: No Topics: Array, Binary Search, Counting

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

In nums, 0 is neither positive nor negative.

• Examples
• Constraints
• Linear Scan
• Binary Search
• Built-in Library Functions

Examples

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 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 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 is 4.

Constraints

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

Linear Scan

Intuition Iterate through the array once, counting the number of negative and positive integers separately, then return the larger count.

Steps

• Initialize two counters, neg and pos, to 0.
• Loop through each number in the array.
• If the number is less than 0, increment neg.
• If the number is greater than 0, increment pos.
• Return the maximum of neg and pos.

class Solution:
    def maximumCount(self, nums: list[int]) -> int:
        neg = 0
        pos = 0
        for num in nums:
            if num < 0:
                neg += 1
            elif num > 0:
                pos += 1
        return max(neg, pos)

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Simple and effective for small input sizes.

Binary Search

Intuition Since the array is sorted, all negative numbers appear before all non-negative numbers, and all positive numbers appear after all non-positive numbers. We can use binary search to find the boundaries.

Steps

• Find the index i of the first element that is greater than or equal to 0. The count of negative numbers is i.
• Find the index j of the first element that is strictly greater than 0. The count of positive numbers is nums.length - j.
• Return the maximum of the two counts.

class Solution:
    def maximumCount(self, nums: list[int]) -> int:
        def first_non_neg():
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] < 0:
                    left = mid + 1
                else:
                    right = mid
            return left

        def first_pos():
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] <= 0:
                    left = mid + 1
                else:
                    right = mid
            return left

        neg_count = first_non_neg()
        pos_count = len(nums) - first_pos()
        return max(neg_count, pos_count)

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Optimal solution for large datasets.

Built-in Library Functions

Intuition Leverage standard library functions that perform binary search to find the insertion points for 0 and 1, which directly give us the counts.

Steps

• Use the language’s built-in binary search or lower bound function to find the index where 0 would be inserted (count of negatives).
• Use the same function to find the index where 1 would be inserted (count of positives).
• Calculate the difference to get the positive count and return the maximum.

import bisect

class Solution:
    def maximumCount(self, nums: list[int]) -> int:
        neg_count = bisect.bisect_left(nums, 0)
        pos_count = len(nums) - bisect.bisect_left(nums, 1)
        return max(neg_count, pos_count)

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Utilizes optimized library routines for cleaner code.