Maximum Count of Positive Integer and Negative Integer

Easy
274.

Maximum Count of Positive Integer and Negative Integer

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.

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] <= 2000
  • nums is sorted in non-decreasing order.

Follow-up: Can you use the sortedness to answer in O(log n)?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumCount = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    A single pass with two counters is correct and obvious.

  2. Hint 2

    Because the array is sorted, binary search can find the first non-negative and the first positive instead.

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

  1. Count x > 0 and x < 0.
  2. 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