Maximum Count of Positive Integer and Negative Integer
EasyPrompt
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
numsisposand the number of negative integers isneg, then return the maximum ofposandneg.
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] <= 2000numsis sorted in a non-decreasing order.
Follow up: Can you solve the problem in O(log(n)) time complexity?
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. It involves a single pass through the array, where we explicitly count the number of positive and negative integers. We use two variables to keep track of the counts and then return the maximum of the two.
Algorithm
-
- Initialize two counters,
posCountandnegCount, to zero.
- Initialize two counters,
-
- Iterate through each element
numin the input arraynums.
- Iterate through each element
-
- For each
num, check if it is less than 0. If it is, incrementnegCount.
- For each
-
- Check if
numis greater than 0. If it is, incrementposCount.
- Check if
-
- Numbers equal to 0 are skipped.
-
- After the loop completes, return the maximum value between
posCountandnegCount.
- After the loop completes, return the maximum value between
Walkthrough
In this approach, we initialize two integer variables, negCount and posCount, to 0. We then iterate through the nums array using a for-each loop. Inside the loop, for each element num, we check its sign. If num is less than 0, we increment negCount. If num is greater than 0, we increment posCount. We ignore any elements that are equal to 0, as per the problem description. After iterating through all the elements, the two counters will hold the total number of negative and positive integers, respectively. The final step is to return the larger of these two counts using Math.max(posCount, negCount).
class Solution { public int maximumCount(int[] nums) { int posCount = 0; int negCount = 0; for (int num : nums) { if (num > 0) { posCount++; } else if (num < 0) { negCount++; } } return Math.max(posCount, negCount); }}Complexity
Time
O(n), where `n` is the length of the `nums` array. This is because we must visit every element in the array once to determine its sign.
Space
O(1), as we only use a constant amount of extra space for the two counter variables, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
It is a general solution that would also work correctly if the array were not sorted.
Cons
Does not leverage the sorted property of the array, leading to a suboptimal time complexity.
Fails to meet the O(log n) time complexity mentioned in the problem's follow-up.
A much more efficient approach is to use binary search, which takes advantage of the fact that the input array nums is sorted. We can find the number of negative and positive integers by finding the boundaries where negative numbers end and positive numbers begin. This allows us to solve the problem in logarithmic time.
Algorithm
-
- Find the count of negative numbers. This is equivalent to finding the index of the first element that is greater than or equal to 0. This can be done using a binary search helper function. Let's call this count
negCount.
- Find the count of negative numbers. This is equivalent to finding the index of the first element that is greater than or equal to 0. This can be done using a binary search helper function. Let's call this count
-
- Find the count of positive numbers. This is equivalent to the total length of the array minus the index of the first element that is strictly greater than 0. This can also be found using a binary search helper function. Let's call this count
posCount.
- Find the count of positive numbers. This is equivalent to the total length of the array minus the index of the first element that is strictly greater than 0. This can also be found using a binary search helper function. Let's call this count
-
- Return the maximum of
negCountandposCount.
- Return the maximum of
Walkthrough
Since the array is sorted in non-decreasing order, all negative numbers will be at the beginning, followed by zeros, and then positive numbers at the end. We can use binary search to find the transition points.
-
Count of Negative Numbers: The number of negative integers is the same as the index of the first non-negative number (i.e., the first element
>= 0). We can find this index, which represents the 'lower bound' for 0, using a binary search. Let's say this index isfirstNonNegativeIdx. Then,negCount = firstNonNegativeIdx. -
Count of Positive Numbers: The number of positive integers is the total length of the array minus the index of the first positive number (i.e., the first element
> 0). This index is the 'upper bound' for 0. Let's say this index isfirstPositiveIdx. Then,posCount = nums.length - firstPositiveIdx.
We can implement two helper functions that perform binary search to find these indices. After obtaining both counts, we return their maximum.
class Solution { public int maximumCount(int[] nums) { // Count of negative numbers is the index of the first element >= 0. int negCount = findLowerBound(nums, 0); // Count of positive numbers is n - (index of the first element > 0). int posCount = nums.length - findUpperBound(nums, 0); return Math.max(negCount, posCount); } // Finds the index of the first element >= target (lower bound). private int findLowerBound(int[] nums, int target) { int low = 0, high = nums.length - 1; int ans = nums.length; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] >= target) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } // Finds the index of the first element > target (upper bound). private int findUpperBound(int[] nums, int target) { int low = 0, high = nums.length - 1; int ans = nums.length; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] > target) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; }}Complexity
Time
O(log n), where `n` is the length of the `nums` array. This is because the dominant operations are two binary searches, each of which takes logarithmic time.
Space
O(1), as the binary search is performed in-place and only requires a few variables to keep track of indices, using constant extra space.
Trade-offs
Pros
Highly efficient, with a time complexity of O(log n).
This is the optimal solution for the problem as it fully utilizes the sorted property of the input.
Satisfies the follow-up requirement.
Cons
The implementation is more complex than a simple linear scan.
Requires careful implementation of binary search to handle edge cases correctly (e.g., arrays with all positive, all negative, or all zero elements).
Solutions
Solution
class Solution {public int maximumCount(int[] nums) { int a = 0, b = 0; for (int v : nums) { if (v > 0) { ++a; } if (v < 0) { ++b; } } return Math.max(a, b); }}class Solution {public: int maximumCount(vector<int> &nums) { int a = 0, b = 0; for (int &v : nums) { if (v > 0) { ++a; } if (v < 0) { ++b; } } return max(a, b); }};class Solution: def maximumCount(self, nums: List[int]) -> int: a = sum(v > 0 for v in nums) b = sum(v < 0 for v in nums) return max(a, b)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.