Maximum Count of Positive Integer and Negative Integer

Maximum Count of Positive Integer and Negative Integer - 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 nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.

Note: 0 is neither positive nor negative.

Input & Output

Example 1 — More Negatives

$ Input: nums = [-2,-1,-1,1,2,3]

› Output: 3

💡 Note: There are 3 negative integers and 3 positive integers. Return max(3, 3) = 3.

Example 2 — More Positives

$ Input: nums = [-3,-2,-1,0,0,1,2]

› Output: 3

💡 Note: There are 3 negative integers and 2 positive integers. Return max(3, 2) = 3.

Example 3 — Only Positives

$ Input: nums = [5,20,66,1314]

› Output: 4

💡 Note: There are 0 negative integers and 4 positive integers. Return max(0, 4) = 4.

Constraints

1 ≤ nums.length ≤ 2000
-2000 ≤ nums[i] ≤ 2000
nums is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input Array

Sorted array with negative, zero, and positive numbers

Count Each Type

Count negatives and positives (ignore zeros)

Return Maximum

Return the larger of the two counts

Key Takeaway

🎯 Key Insight: Use the sorted property to find boundaries efficiently with binary search instead of counting every element

Asked in

M Microsoft 15 a Amazon 12 🍎 Apple 8

The key insight is to leverage the sorted property of the array. While a linear scan works in O(n), we can use binary search to find the boundaries between negative, zero, and positive numbers in O(log n) time. Best approach depends on array size: linear for small arrays, binary search for large ones. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Count	O(n)	O(1)	Count positive and negative numbers by iterating through the entire array
Binary Search Optimization	O(log n)	O(1)	Use binary search to find boundaries between negative, zero, and positive numbers

Linear Count — Algorithm Steps

Initialize counters for positive and negative numbers
Iterate through array and count each type
Return the maximum of the two counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Counters

Start with pos_count = 0, neg_count = 0

Scan Array

Check each element and increment appropriate counter

Compare

Return maximum of the two counts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int posCount = 0;
    int negCount = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > 0) {
            posCount++;
        } else if (nums[i] < 0) {
            negCount++;
        }
    }
    
    return posCount > negCount ? posCount : negCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all n elements

✓ Linear Growth

Space Complexity

O(1)

Only uses two counter variables

✓ Linear Space

35.0K Views

Medium Frequency

~10 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler