Problem Statement

Given an array nums sorted in increasing order, return the maximum between the count of positive integers and the count of negative integers.

Note: 0 is neither positive nor negative.

Examples

Example 1:

• Input: nums = [-4, -3, -1, 0, 1, 3, 5, 7]
• Expected Output: 4
• Justification: The array contains three negative integers (-4, -3, -1) and four positive integers (1, 3, 5, 7). The maximum count between negatives and positives is 4.

Example 2:

• Input: nums = [-8, -7, -5, -4, 0, 0, 0]
• Expected Output: 4
• Justification: Here, there are four negative integers (-8, -7, -5, -4) and no positives. Thus, the maximum count is 4.

Example 3:

• Input: nums = [0, 2, 2, 3, 3, 3, 4]
• Expected Output: 6
• Justification: This input array includes zero negative integers and six positives (2, 2, 3, 3, 3, 4). Hence, the maximum count is 6.

Constraints:

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

Solution

To solve this problem, the primary approach involves efficiently counting the positive and negative numbers in the sorted array. Given the array is already sorted, we can leverage this property by using binary search to quickly determine the boundary between negative and positive integers, optimizing the count operation. This boundary identification will allow for rapid determination of the counts of negative and positive integers without having to iterate through every element, thus promising a time-efficient solution.

The sorted nature of the array ensures that once we find the first positive integer, all subsequent integers are positive, allowing this method to be particularly effective.

Step-by-step Algorithm

1. Initialization:

   • Declare and initialize start to 0 and end to nums.length - 1.
   • Initialize maxNegatives and maxPositives to 0 to store the maximum counts of negative and positive numbers respectively.

2. First Pass: Counting Negative Numbers:

   • While start is less than or equal to end:
     • Compute the midpoint mid = start + (end - start) / 2.
     • If nums[mid] < 0, it indicates that we still have negative numbers:
       • Update maxNegatives to mid + 1 since this counts how many elements are negative (indices from 0 to mid).
       • Set start to mid + 1 to continue searching to the right of mid.
     • Else, adjust end to mid - 1 to search in the left half for more negatives.

3. Second Pass: Counting Positive Numbers:

   • Reset start to 0 and end to nums.length - 1.
   • While start is less than or equal to end:
     • Compute the midpoint mid = start + (end - start) / 2.
     • If nums[mid] > 0, it indicates that we are in the range of positive numbers:
       • Update maxPositives to nums.length - mid to count all positive numbers from mid to the end of the array.
       • Set end to mid - 1 to continue searching to the left of mid for the start of positive numbers.
     • Else, adjust start to mid + 1 to search in the right half for the first positive number.

4. Return the Maximum Count:

   • Use the Math.max function to determine and return the maximum of maxNegatives and maxPositives.

Algorithm Walkthrough

Let's consider the input: nums = [-4, -3, -1, 0, 1, 3, 5, 7].

1. Counting Negative Numbers:

   • Start with start = 0, end = 7.
   • Iteration 1: mid = 3, value at mid is 0. Adjust end to 2.
   • Iteration 2: mid = 1, value at mid is -3. It is negative, so update maxNegatives to 2 and move start to 2.
   • Iteration 3: mid = 2, value at mid is -1. It is negative, so update maxNegatives to 3 and move start to 3.
   • No more elements to the left; loop exits with maxNegatives = 3.

2. Counting Positive Numbers:

   • Reset with start = 0, end = 7.
   • Iteration 1: mid = 3, value at mid is 0. Adjust start to 4.
   • Iteration 2: mid = 5, value at mid is 3. It is positive, so update maxPositives to 3 and move end to 4.
   • Iteration 3: mid = 4, value at mid is 1. It is positive, so update maxPositives to 4 and move end to 3.
   • No more elements to the right; loop exits with maxPositives = 4.

3. Maximum Count:

   • maxNegatives = 3 and maxPositives = 4.
   • Final result is Math.max(3, 4) which yields 4.