Maximum Count of Positive Integer and Negative Integer solution and explanation
Google
9 more videos on this problem
Maximum Count of Positive Integer and Negative Integer | Leetcode 2529Techdose · 6:15 · 3K views
2529. Maximum Count of Positive Integer and Negative Integer | leetcode daily challenge dsaShashCode · 15:17 · 2K views
LeetCode 2529. Maximum Count of Positive Integer and Negative Integer - Interview Prep Ep 127Fisher Coder · 5:14 · 2K views
Leetcode | 2529. Maximum Count of Positive Integer and Negative Integer | Easy | Java SolutionDeveloper Docs · 4:03 · 1K views
2529. Maximum Count of Positive Integer and Negative Integer (Leetcode Easy)Programming Live with Larry · 2:42 · 709 views
Leetcode 2529 Maximum Count of Positive Integer and Negative Integer (Java) - Leetcode Contest 327TheAnalyticGuy · 1:41 · 460 views
Maximum Count of Positive Integer and Negative Integer Leetcode | Leetcode Question 2529 | EasySolving It · 3:49 · 316 views
Maximum Count of Positive Integer and Negative Integer - Leetcode 2529 - PythonTim Huang · 5:34 · 251 views
2529. Maximum Count of Positive Integer and Negative Integer | Leetcode with JavaScript #leetcodeArsalan Ahmed · 5:20 · 173 views
2529. Maximum Count of Positive Integer and Negative Integer | Leetcode Daily - PythonLeetcode Daily · 3:52 · 168 views
The problem
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?
Approach overview
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.
Approach 1: Approach 1: Linear Scan
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.
def maximum_count(nums):
neg, pos = 0, 0
for num in nums:
if num < 0:
neg += 1
elif num > 0:
pos += 1
return max(pos, neg)
nums = [-3, -2, -1, 0, 0, 1, 2]
print(maximum_count(nums))public class Solution {
public static int maximumCount(int[] nums) {
int neg = 0, pos = 0;
for (int num : nums) {
if (num < 0) {
neg++;
} else if (num > 0) {
pos++;
}
}
return Math.max(pos, neg);
}
public static void main(String[] args) {
int[] nums = {-3, -2, -1, 0, 0, 1, 2};
System.out.println(maximumCount(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int maximumCount(vector<int>& nums) {
int neg = 0, pos = 0;
for (int num : nums) {
if (num < 0) {
neg++;
} else if (num > 0) {
pos++;
}
}
return max(pos, neg);
}
int main() {
vector<int> nums = {-3, -2, -1, 0, 0, 1, 2};
cout << maximumCount(nums) << endl;
return 0;
}function maximumCount(nums) {
let neg = 0, pos = 0;
nums.forEach((num) => {
if (num < 0) neg++;
else if (num > 0) pos++;
});
return Math.max(pos, neg);
}
let nums = [-3, -2, -1, 0, 0, 1, 2];
console.log(maximumCount(nums));#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int maximumCount(int* nums, int numsSize) {
int neg = 0, pos = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] < 0) {
neg++;
} else if (nums[i] > 0) {
pos++;
}
}
return max(pos, neg);
}
int main() {
int nums[] = {-3, -2, -1, 0, 0, 1, 2};
int result = maximumCount(nums, 7);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public static int MaximumCount(int[] nums) {
int neg = 0, pos = 0;
foreach (int num in nums) {
if (num < 0) {
neg++;
} else if (num > 0) {
pos++;
}
}
return Math.Max(pos, neg);
}
public static void Main(string[] args) {
int[] nums = {-3, -2, -1, 0, 0, 1, 2};
Console.WriteLine(MaximumCount(nums));
}
}The Python code counts negative and positive numbers using a simple loop and returns the maximum count.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Approach 2: Binary Search
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.
def binary_search_positive(nums):
low, high = 0, len(nums)
while low < high:
mid = (low + high) // 2
if nums[mid] <= 0:
low = mid + 1
else:
high = mid
return low
def binary_search_non_negative(nums):
low, high = 0, len(nums)
while low < high:
mid = (low + high) // 2
if nums[mid] < 0:
low = mid + 1
else:
high = mid
return low
def maximum_count(nums):
pos = len(nums) - binary_search_positive(nums)
neg = binary_search_non_negative(nums)
return max(pos, neg)
nums = [-3, -2, -1, 0, 0, 1, 2]
print(maximum_count(nums))public class Solution {
private static int firstNonNegative(int[] nums) {
int low = 0, high = nums.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < 0) low = mid + 1;
else high = mid;
}
return low;
}
private static int firstPositive(int[] nums) {
int low = 0, high = nums.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] <= 0) low = mid + 1;
else high = mid;
}
return low;
}
public static int maximumCount(int[] nums) {
int pos = nums.length - firstPositive(nums);
int neg = firstNonNegative(nums);
return Math.max(pos, neg);
}
public static void main(String[] args) {
int[] nums = {-3, -2, -1, 0, 0, 1, 2};
System.out.println(maximumCount(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int binarySearchPositive(vector<int>& nums) {
int low = 0, high = nums.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] <= 0) low = mid + 1;
else high = mid;
}
return low;
}
int binarySearchNonNegative(vector<int>& nums) {
int low = 0, high = nums.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < 0) low = mid + 1;
else high = mid;
}
return low;
}
int maximumCount(vector<int>& nums) {
int firstPositive = binarySearchPositive(nums);
int firstNonNegative = binarySearchNonNegative(nums);
int pos = nums.size() - firstPositive;
int neg = firstNonNegative;
return max(pos, neg);
}
int main() {
vector<int> nums = {-3, -2, -1, 0, 0, 1, 2};
cout << maximumCount(nums) << endl;
return 0;
}function binarySearchPositive(nums) {
let low = 0, high = nums.length;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (nums[mid] <= 0) low = mid + 1;
else high = mid;
}
return low;
}
function binarySearchNonNegative(nums) {
let low = 0, high = nums.length;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (nums[mid] < 0) low = mid + 1;
else high = mid;
}
return low;
}
function maximumCount(nums) {
let pos = nums.length - binarySearchPositive(nums);
let neg = binarySearchNonNegative(nums);
return Math.max(pos, neg);
}
let nums = [-3, -2, -1, 0, 0, 1, 2];
console.log(maximumCount(nums));#include <stdio.h>
int binarySearchNonNegative(int* nums, int numsSize) {
int low = 0, high = numsSize;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < 0) low = mid + 1;
else high = mid;
}
return low;
}
int binarySearchPositive(int* nums, int numsSize) {
int low = 0, high = numsSize;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] <= 0) low = mid + 1;
else high = mid;
}
return low;
}
int maximumCount(int* nums, int numsSize) {
int firstPositive = binarySearchPositive(nums, numsSize);
int firstNonNegative = binarySearchNonNegative(nums, numsSize);
int pos = numsSize - firstPositive;
int neg = firstNonNegative;
return pos > neg ? pos : neg;
}
int main() {
int nums[] = {-3, -2, -1, 0, 0, 1, 2};
int result = maximumCount(nums, 7);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
private static int FirstNonNegative(int[] nums) {
int low = 0, high = nums.Length;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < 0) low = mid + 1;
else high = mid;
}
return low;
}
private static int FirstPositive(int[] nums) {
int low = 0, high = nums.Length;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] <= 0) low = mid + 1;
else high = mid;
}
return low;
}
public static int MaximumCount(int[] nums) {
int pos = nums.Length - FirstPositive(nums);
int neg = FirstNonNegative(nums);
return Math.Max(pos, neg);
}
public static void Main(string[] args) {
int[] nums = {-3, -2, -1, 0, 0, 1, 2};
Console.WriteLine(MaximumCount(nums));
}
}Python's approach using binary search functions to ascertain the counts for computation of maximal subset size.
Time Complexity: O(log n).
Space Complexity: O(1).
Approach 3: Traversal
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).
function maximumCount(nums: number[]): number {
let [a, b] = [0, 0];
for (const x of nums) {
if (x > 0) {
++a;
} else if (x < 0) {
++b;
}
}
return Math.max(a, b);
}func maximumCount(nums []int) int {
var a, b int
for _, x := range nums {
if x > 0 {
a++
} else if x < 0 {
b++
}
}
return max(a, b)
}impl Solution {
pub fn maximum_count(nums: Vec<i32>) -> i32 {
let mut a = 0;
let mut b = 0;
for x in nums {
if x > 0 {
a += 1;
} else if x < 0 {
b += 1;
}
}
std::cmp::max(a, b)
}
}Approach 4: Binary Search
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).
function maximumCount(nums: number[]): number {
const search = (x: number): number => {
let [left, right] = [0, nums.length];
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
const i = search(1);
const j = search(0);
const [a, b] = [nums.length - i, j];
return Math.max(a, b);
}func maximumCount(nums []int) int {
a := len(nums) - sort.SearchInts(nums, 1)
b := sort.SearchInts(nums, 0)
return max(a, b)
}impl Solution {
fn search(nums: &Vec<i32>, x: i32) -> usize {
let mut left = 0;
let mut right = nums.len();
while left < right {
let mid = (left + right) >> 1;
if nums[mid] >= x {
right = mid;
} else {
left = mid + 1;
}
}
left
}
pub fn maximum_count(nums: Vec<i32>) -> i32 {
let n = nums.len();
let i = Self::search(&nums, 1);
let j = Self::search(&nums, 0);
(n - i).max(j) as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Linear Scan | Time Complexity: O(n). |
| Approach 2: Binary Search | Time Complexity: O(log n). |
| Traversal | – |
| Binary Search | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximum Count of Positive Integer and Negative Integer easy or hard?
LeetCode classifies this problem as Easy. The core logic is simple counting, while the binary search optimization adds a small twist that tests whether you recognize the array is sorted.
Maximum Count of Positive Integer and Negative Integer Python/Java solution
Both Python and Java implementations typically follow two patterns: a linear scan that counts positives and negatives in one pass, or a binary search solution that finds the first positive index and the first non-negative index. The binary search approach runs in O(log n) time.
How to solve Maximum Count of Positive Integer and Negative Integer in O(n)?
Traverse the array once and maintain two counters: one for numbers less than zero and another for numbers greater than zero. Ignore zeros during counting. After the loop, return the maximum of the two counters. This linear scan takes O(n) time and O(1) space.
What is the best approach for Maximum Count of Positive Integer and Negative Integer?
The optimal approach uses binary search because the array is already sorted. By locating the first non‑negative number and the first positive number, you can compute the counts of negatives and positives in O(log n) time with O(1) space.
Is Maximum Count of Positive Integer and Negative Integer asked at Google/Amazon/Meta?
Problems involving counting elements in sorted arrays and applying binary search boundaries are common interview patterns at companies like Google, Amazon, and Meta. Variants of this problem appear in screening rounds to test understanding of binary search and array traversal.
What data structure is used in Maximum Count of Positive Integer and Negative Integer?
The problem primarily uses an array. The optimized solution applies binary search on the sorted array to find boundary indices where negative numbers end and positive numbers begin.
What is the time complexity of Maximum Count of Positive Integer and Negative Integer?
The straightforward solution runs in O(n) time by scanning the array once and counting positives and negatives. Using binary search on the sorted array improves the runtime to O(log n) while still using constant extra space.