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.
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); }}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.