We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Count of Positive Integer and Negative Integer

Number: 2614

Difficulty: Easy

Paid? No

Companies: Bloomberg, Amazon, ShareChat

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 the array. Note that 0 is neither positive nor negative.

Key Insights

  • The array is already sorted, so binary search can be used to efficiently locate boundaries.
  • Find the count of negative numbers by locating the first index where the number is no longer negative (i.e., >= 0).
  • Find the count of positive numbers by locating the first index where the number is strictly positive (i.e., >= 1).
  • Use the maximum of these counts as the final answer.
  • Although a linear scan takes O(n) time, binary search reduces the time complexity to O(log n).

Space and Time Complexity

Time Complexity: O(log n) Space Complexity: O(1)

Solution

We perform two binary searches:

  1. The first binary search identifies the leftmost position of 0. The count of negatives is exactly the index of this position.
  2. The second binary search identifies the leftmost position of 1. The count of positives is the total length of the array minus this index. Return the maximum of these two counts. This approach leverages the sorted nature of the array for efficient boundary detection.

Code Solutions

# Python solution with binary search

def maximumCount(nums):
    # Helper function to find the leftmost index such that nums[i] >= target.
    def binary_search_leftmost(target):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    # Find count of negative numbers (elements less than 0)
    first_non_negative = binary_search_leftmost(0)
    negative_count = first_non_negative

    # Find count of positive numbers (elements greater than 0)
    first_positive = binary_search_leftmost(1)
    positive_count = len(nums) - first_positive

    # Return the maximum count between negatives and positives.
    return max(negative_count, positive_count)

# Example usage:
nums1 = [-2, -1, -1, 1, 2, 3]
print(maximumCount(nums1))  # Expected output: 3
← Back to All Questions