Skip to main content
Talentd

Maximum Count of Positive Integer and Negative Integer - Solution & Explanation

EasyArrayBinary SearchCounting20 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 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] <= 2000
  • nums is 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1) as only a few additional variables are used.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n).
Space Complexity: O(1).

Try this approach in the editor →

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

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

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

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Linear Scan

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1) as only a few additional variables are used.

Approach 2: Binary Search

Time Complexity: O(log n).
Space Complexity: O(1).

Traversal—
Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)General solution; works even if the array is not sorted
Binary Search BoundariesO(log n)O(1)Best when the array is sorted and you want optimal runtime

Video Solution

Maximum Count of Positive Integer and Negative Integer | Leetcode 2529 • Techdose • 3,141 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Count of Positive Integer and Negative Integer with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Search

Next

Count Negative Numbers in a Sorted Matrix