Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.
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.
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 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,20,66,1314] Output: 4 Explanation: There are 4 positive integers and 0 negative integers. The maximum count among them is 4.
Constraints:
1 <= nums.length <= 2000-2000 <= nums[i] <= 2000nums is sorted in a non-decreasing order.Follow up: Can you solve the problem in O(log(n)) time complexity?
In #2529 Maximum Count of Positive Integer and Negative Integer, you are given a non-decreasing sorted array and must return the larger value between the number of positive integers and the number of negative integers. Zeros are ignored in the count.
A straightforward idea is to scan the array once and count how many elements are less than zero and greater than zero. Since the array is already sorted, you can also take advantage of binary search to find the boundary between negative numbers, zeros, and positive numbers. Specifically, locate the first index where numbers become >= 0 and the first index where numbers become > 0.
From these boundaries, you can compute the counts of negative and positive elements without iterating through the entire array. The final answer is simply the max(negativeCount, positiveCount). A linear scan works in O(n) time, while the binary search approach improves it to O(log n) time with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Linear Scan Counting | O(n) | O(1) |
| Binary Search on Sorted Array | O(log n) | O(1) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
Count how many positive integers and negative integers are in the array.
Since the array is sorted, can we use the binary search?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, you can solve it with a simple linear scan of the array. Count the number of values less than zero and greater than zero, then return the maximum of the two counts. This approach runs in O(n) time and O(1) space.
While this exact problem may not frequently appear in FAANG interviews, the concepts behind it—binary search on sorted arrays and counting elements based on conditions—are very common in technical interviews.
No special data structure is required for this problem. Since the input is already a sorted array, simple counting or binary search on the array is sufficient to efficiently determine the number of positive and negative elements.
The optimal approach leverages the fact that the array is sorted. By using binary search to locate the first non-negative element and the first positive element, you can compute the counts of negative and positive numbers in O(log n) time.