2529.Maximum_Count_of_Positive_Integer_and_Negative_Integer(Easy).md

2529. Maximum Count of Positive Integer and Negative Integer (Easy)

Date and Time: Mar 11, 2025, 23:08 (EST)

Link: https://leetcode.com/problems/maximum-count-of-positive-integer-and-negative-integer

Question:

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.

Walk-through:

We notice the 0 separate the negative number and the positive number.

First, initliaze start, end = len(nums), len(nums), because we only update start when we find the beginning of 0 or the first positive number. Update end when we find the end of 0 or the end of negative number.

start to find the first index that nums[start] >= 0, end to find the first index that great than zero. start can tell how many negative integers, and len(nums)-end can tell how many positive integers.

Binary Search Solution:

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        # Because 0 divides the neg int and pos int, run Binary Search to find start index >= 0, and end index > 0
        # Start tells how many neg int, len(nums)-end tells how many pos int

        # TC: O(log(n)), n=len(nums), SC: O(1)
        l, r = 0, len(nums)-1
        # Start: first index >= 0, end: first index > 0
        start, end = len(nums), len(nums)
        while l <= r:
            m = (l+r)//2
            # Update start to be smaller for valid pos
            if nums[m] >= 0:
                start = m
                r = m - 1
            else:
                l = m + 1

        # Second BS
        l, r = 0, len(nums)-1
        while l <= r:
            m = (l+r)//2
            # Update to find the smaller valid end
            if nums[m] > 0:
                end = m
                r = m - 1
            else:
                l = m + 1
        return max(start, len(nums)-end)

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

Brute Force Solution:

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        # Brute force: for i in nums, if i < 0, neg+=1, elif i > 0, pos+=1. return max(neg, pos)

        # TC: O(n), SC: O(1)
        pos, neg = 0, 0
        for i in nums:
            if i < 0:
                neg += 1
            elif i > 0:
                pos += 1
        return max(pos, neg)

Time Complexity: $O(n)$
Space Complexity: $O(1)$