Maximum Count of Positive Integer and Negative Integer Solution
Maximum Count of Positive Integer and Negative Integer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Count of Positive Integer and Negative Integer is an easy coding problem on arrays, binary search and counting, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Binary Search, Counting
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array nums sorted in non-decreasing order, count the positive integers and the negative integers separately and return the larger of the two counts.
Note that 0 is neither positive nor negative.
Example 1
Input: nums = [-2,-1,-1,1,2,3]
Output: 3
Explanation: Three negatives and three positives — the maximum is 3.
Example 2
Input: nums = [-3,-2,-1,0,0,1,2]
Output: 3
Explanation: Three negatives beat two positives.
Example 3
Input: nums = [5,20,66,1314]
Output: 4
Constraints
1 <= nums.length <= 40-2000 <= nums[i] <= 2000nums is sorted in non-decreasing order.
Follow-up: Can you use the sortedness to answer in O(log n)?
Hints for Maximum Count of Positive Integer and Negative Integer
Hint 1
A single pass with two counters is correct and obvious.
Hint 2
Because the array is sorted, binary search can find the first non-negative and the first positive instead.
Hint 3
Zeros belong to neither group — do not let them inflate either count.
How to solve Maximum Count of Positive Integer and Negative Integer
Count positives and negatives separately, ignoring zeros, and return the larger.
Approach
- Count
x > 0andx < 0. - Return the maximum.
Why it works
Zero is neither positive nor negative, so the two strict comparisons partition the relevant elements exactly.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Because the array is sorted, two binary searches (first
>= 0, first> 0) give O(log n).
Reference solution
Python
def maximumCount(nums) -> int:
pos = sum(1 for x in nums if x > 0)
neg = sum(1 for x in nums if x < 0)
return max(pos, neg)Java
public static int maximumCount(int[] nums) {
int pos = 0, neg = 0;
for (int v : nums) {
if (v > 0) pos++;
else if (v < 0) neg++;
}
return Math.max(pos, neg);
}C++
int maximumCount(vector<int>& nums) {
int pos = 0, neg = 0;
for (int v : nums) {
if (v > 0) pos++;
else if (v < 0) neg++;
}
return max(pos, neg);
}JavaScript
var maximumCount = function(nums) {
let pos = 0, neg = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) pos++;
else if (nums[i] < 0) neg++;
}
return pos > neg ? pos : neg;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search