Teaching Kids Programming – Maximum Count of Positive Integer and Negative Integer in Sorted Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

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?

Hints:
Count how many positive integers and negative integers are in the array.
Since the array is sorted, can we use the binary search?

Maximum Count of Positive Integer and Negative Integer (Sorted Array, Bruteforce)

Even it is sorted, we can simply iterate over the numbers and count the postive and negatives. This results in a simple solution which is O(N) time and O(1) space.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        p = 0
        n = 0
        for i in nums:
            if i > 0:
                p += 1
            elif i < 0:
                n += 1
        return max(p, n)

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        p = 0
        n = 0
        for i in nums:
            if i > 0:
                p += 1
            elif i < 0:
                n += 1
        return max(p, n)

We can do this using one-liner, however, this takes Two Passes, even the time complexity is still O(N):

1
2
3

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        return max(sum(i > 0 for i in nums), sum(i < 0 for i in nums))

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        return max(sum(i > 0 for i in nums), sum(i < 0 for i in nums))

We can make a small improvement by exiting the loop once we meet any positive numbers – which then can be computed using the simple math.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        p = 0
        n = 0
        for i, v in enumerate(nums):
            if v > 0:
                p = len(nums) - i
                break
            elif v < 0:
                n += 1
        return max(p, n)       

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        p = 0
        n = 0
        for i, v in enumerate(nums):
            if v > 0:
                p = len(nums) - i
                break
            elif v < 0:
                n += 1
        return max(p, n)       

The time complexity is still O(N) as in the worst case, when there are no positive numbers, the optimisation part is n

Maximum Count of Positive Integer and Negative Integer (Sorted Array, Binary Search Algorithm)

When the array is sorted, we can binary search the leftmost zero and right most zero – using the bisect_left and bisect_right. The returned two indices can be used to count how many negative and positive numbers.

1
2
3
4
5

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        n = bisect_left(nums, 0)
        p = len(nums) - bisect_right(nums, 0)
        return max(p, n)

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        n = bisect_left(nums, 0)
        p = len(nums) - bisect_right(nums, 0)
        return max(p, n)

This brings down the time complexity to O(logN).

–EOF (The Ultimate Computing & Technology Blog) —