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.

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.

Description Hints 2 Solution Video 6:15

2529. Maximum Count of Positive Integer and Negative Integer

Q: 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.

Q: 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.

Easy74.3% acceptance5 companies

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?

Asked at 5 companies

ShareChat

Google Amazon Microsoft Meta

Topics

Hints open one at a time

Hint 1

Count how many positive integers and negative integers are in the array.

Hint 2

Since the array is sorted, can we use the binary search?

6:15

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution