Maximum Count of Positive Integer and Negative Integer

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.

Key Insights

• The array is sorted, allowing efficient counting.
• Positive integers are greater than 0, while negative integers are less than 0.
• Zero is neither positive nor negative and should be ignored in the counts.
• We can utilize binary search to find the transition point between negative and positive integers.

Space and Time Complexity

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

Solution

To solve the problem, we can use a binary search algorithm to efficiently find the number of negative and positive integers in the sorted array. Given that the array is sorted, we can find the index where positive integers start, which allows us to count both negative and positive integers easily.

1. Perform binary search to find the first positive integer's index.
2. The number of negative integers can be calculated as this index (since all elements before it are negative).
3. The number of positive integers is the total length of the array minus this index.
4. Finally, return the maximum of the two counts.

Code Solutions