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?
Problem Overview: You receive a non-decreasing sorted integer array. The goal is simple: count how many values are negative and how many are positive, ignore zeros, and return whichever count is larger.
The sorted property of the array is the key detail. A straightforward solution scans the entire array and counts values. A more optimized approach uses binary search to directly locate the boundaries between negative numbers, zeros, and positive numbers.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest approach is to iterate through the array once and maintain two counters: one for negative numbers and one for positive numbers. For each element, check if it is less than zero or greater than zero and increment the corresponding counter. Zeros are ignored because they are neither positive nor negative. After the traversal, return max(negativeCount, positiveCount). This approach works for any array regardless of sorting and is often the first solution you write in an interview to demonstrate basic correctness. The algorithm performs a single pass through the array, so the time complexity is O(n) and the space complexity is O(1).
Approach 2: Binary Search (O(log n) time, O(1) space)
Because the array is already sorted, you can use binary search to find boundaries instead of scanning the entire list. First find the index of the first element greater than zero (the first positive number). Then find the index of the first element greater than or equal to zero to determine where negative numbers stop. The number of negatives equals the index of the first non-negative element, and the number of positives equals n - firstPositiveIndex. These two searches run in O(log n) time and require constant extra space. This technique relies on efficient boundary detection rather than explicit iteration, which is a common pattern when solving counting problems on sorted arrays.
Recommended for interviews: Start with the linear scan to show correctness and clarity. Then mention the binary search optimization since the array is sorted. Interviewers typically expect you to recognize this property and reduce the runtime from O(n) to O(log n) using boundary searches.
This approach involves a simple linear scan through the array to count the number of negative and positive integers. As the array is sorted, all negative numbers will appear before non-negative numbers and all positive numbers after non-positive numbers.
This C code defines a function maximumCount which iterates through the given array nums, counts the positive and negative integers, and returns the maximum count of either positive or negative integers. Note that zero is ignored during counting.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1) as only a few additional variables are used.
Use binary search to find the first non-negative and the first positive number. Given the sorted property, this allows us to find the boundaries efficiently. The number of negative integers is equivalent to the index of the first non-negative integer, while the number of positive integers is the total length minus the index of the first positive integer.
This C code uses two binary search functions to find the index of the first non-negative and first positive numbers. By calculating the numbers of positives and negatives based on these indices, the maximum can be found in log time.
Time Complexity: O(log n).
Space Complexity: O(1).
We can directly traverse the array, count the number of positive and negative integers a and b, and return the larger of a and b.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Since the array is sorted in non-decreasing order, we can use binary search to find the index i of the first element that is greater than or equal to 1, and the index j of the first element that is greater than or equal to 0. The number of positive integers is a = n - i, and the number of negative integers is b = j. We return the larger of a and b.
The time complexity is O(log n), where n is the length of the array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Linear Scan | Time Complexity: O(n), where n is the length of the array. |
| Approach 2: Binary Search | Time Complexity: O(log n). |
| Traversal | — |
| Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | General solution; works even if the array is not sorted |
| Binary Search Boundaries | O(log n) | O(1) | Best when the array is sorted and you want optimal runtime |
Maximum Count of Positive Integer and Negative Integer | Leetcode 2529 | codestorywithMIK • codestorywithMIK • 4,692 views views
Watch 9 more video solutions →Practice Maximum Count of Positive Integer and Negative Integer with our built-in code editor and test cases.
Practice on FleetCode