Maximum Count of Positive Integer and Negative Integer

Problem Statement

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:

Input: nums = [-2, -1, -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, 6, 7, 8, 9]
Output: 5

Explanation: There are 5 positive integers and 0
negative integers.
The maximum count among them is 5.

Constraints:

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

If possible try to solve in O(log (n)) time complexity.

Different Approaches

1️⃣ Linear Search

 class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int pos = 0, neg = 0;
        for (auto x : nums) {
            // count positive numbers
            if (x > 0) pos += 1;
            // count negative numbers
            if (x < 0) neg += 1;
        }
        // take the max of pos and neg
        return max(pos, neg);
    }
};

2️⃣ Binary Search

Intuition:

Approach and Steps:

1. Identify the First Positive Element:
   • We perform a binary search to find the index of the first positive element (an element strictly greater than 0).
   • Since the array is sorted, once we locate the first positive element, all elements to the left of this index are non-positive (either negative or zero).
   • Logic: We start with the entire array and check the middle element:
     • If it’s positive, this element could be the first positive, so we store its index in firstPositiveIndex and continue searching in the left half to see if there’s an earlier positive.
     • If it’s zero or negative, then we move to the right half since any positive numbers, if they exist, must be there.
   • After the loop, if we found a positive number, firstPositiveIndex will hold its index; otherwise, it will remain at -1 (indicating no positives).
2. Count Positive Numbers:
   • If firstPositiveIndex is not -1, the count of positive numbers is simply the number of elements from firstPositiveIndex to the end of the array. This is calculated as n - firstPositiveIndex.
3. Identify the Last Negative Element:
   • Similarly, we perform a binary search to find the last negative element (an element strictly less than 0).
   • Once we locate the last negative element, we know that all elements from the start of the array up to this index are negative (since zeros and positives appear afterward).
   • Logic: Starting with the whole array:
     • If the middle element is negative, we store its index in lastNegativeIndex and continue searching to the right to see if there’s a later negative element.
     • If it’s zero or positive, we move to the left half because any negatives must be there.
   • After the loop, if we found a negative number, lastNegativeIndex will hold its index; otherwise, it remains at -1 (indicating no negatives).
4. Count Negative Numbers:
   • If lastNegativeIndex is not -1, the count of negative numbers is simply the number of elements from the start of the array up to lastNegativeIndex + 1.
5. Result:
   • Finally, we return the maximum of positiveCount and negativeCount.

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int n = nums.size();
        
        int firstPositiveIndex = -1; // Index of the first positive number, default to -1 if no positive numbers
        int lastNegativeIndex = -1;  // Index of the last negative number, default to -1 if no negative numbers
        
        int left = 0;   // Left boundary for binary search
        int right = n - 1; // Right boundary for binary search
        
        int positiveCount = 0; // Count of positive numbers
        int negativeCount = 0; // Count of negative numbers
        
        // Binary search to find the first positive number
        while (left <= right) {
            int mid = left + (right - left) / 2; // Calculate the midpoint
            
            if (nums[mid] > 0) {  // Check if the mid element is positive
                firstPositiveIndex = mid; // Update first positive index
                right = mid - 1; // Narrow the search to the left side
            } else {
                left = mid + 1; // Narrow the search to the right side
            }
        }
        
        // Calculate the count of positive numbers
        if (firstPositiveIndex == -1) {
            // If there is no positive number, the count is zero
            positiveCount = 0;
        } else {
            positiveCount = n - firstPositiveIndex; // Count from first positive index to end of array
        }
        
        // Reset left and right boundaries for finding the last negative number
        left = 0;
        right = n - 1;

        // Binary search to find the last negative number
        while (left <= right) {
            int mid = left + (right - left) / 2; // Calculate the midpoint
            
            if (nums[mid] < 0) { // Check if the mid element is negative
                lastNegativeIndex = mid; // Update last negative index
                left = mid + 1; // Narrow the search to the right side
            } else {
                right = mid - 1; // Narrow the search to the left side
            }
        }
        
        // Calculate the count of negative numbers
        if (lastNegativeIndex == -1) {
            // If there are no negative numbers, the count is zero
            negativeCount = 0;
        } else {
            negativeCount = lastNegativeIndex + 1; // Count from start to last negative index (0-based indexing)
        }
        
        // Return the maximum of positive and negative counts
        return max(negativeCount, positiveCount);
    }
};