LeetCode 2529 – Maximum Count of Positive Integer and Negative Integer

The question has been asked by a few companies including Meta, but is not a super popular question.

Nonetheless the question is important as it focusses on a variation of binary search.

The naive solution to the problem would be iterating through the array, finding out the first index you see a positive number, also keeping track the last index you saw a negative number. Then you can then calculate the number of positive numbers and number of negative numbers in the list. But this would be O(n) in time complexity. We can solve this problem by using binary search and this will bring down the time complexity to O(logn).

The trick is to phrase the question as to finding the index of the first occurrence of positive number. Since the array is sorted, we can then calculate the number of positive integers.

We also need to find the last occurence of a negative number in the array. This will then provide us the information about how many negative numbers are there in the array.

Also remember that the array is not guaranteed to have both positive or negative integers, so we need to take that into account as well.

        n = len(nums)

        # First positive index
        l,r = 0,n-1
        first_positive_idx = n
        while l <= r:
            mid = (l+r)//2
            val = nums[mid]
            if val > 0:
                first_positive_idx = mid
                r = mid-1
            else:
                l = mid+1

Here we initialise the first positive index to be n as it may be the case that the array either has all 0s or negative integers, in that case the first positive index has to be outside our array and the first place it can go into is n. We calculate the number of positive integers as n – first_positive_idx, so if it’s at n then we know there are 0 positive integers in the array.

The binary search is the standard binary search, except we search if the value in the middle is positive, if that’s the case we mark that as a possible first positive index and then search towards the left as there could be more positive in the left, otherwise we search in the right half.

        # Last negative index
        l,r = 0,n-1
        last_neg_idx = -1
        while l <= r:
            mid = (l+r)//2
            val = nums[mid]
            if val < 0:
                last_neg_idx = mid
                l = mid + 1
            else:
                r = mid-1

Similarly for the last negative index, we initialise the last negative index to be -1, which is that if all integers in the array are 0 or positive, then its position has to be outside the array. We calculate the number of negative integers as last_negative_idx + 1, so here it will automatically become 0.

We then do a binary search where we check if the middle element is negative, if we find it then we mark it as a possible last negative index and then search towards the right as there could be more negative numbers, otherwise we search in the left half.

Combining everything we have the solution.

class Solution:
    def maximumCount(self, nums: List[int]) -> int:

        
        
        n = len(nums)

        # First positive index
        l,r = 0,n-1
        first_positive_idx = n
        while l <= r:
            mid = (l+r)//2
            val = nums[mid]
            if val > 0:
                first_positive_idx = mid
                r = mid-1
            else:
                l = mid+1
        # Last negative index
        l,r = 0,n-1
        last_neg_idx = -1
        while l <= r:
            mid = (l+r)//2
            val = nums[mid]
            if val < 0:
                last_neg_idx = mid
                l = mid + 1
            else:
                r = mid-1

        num_positive = n-(first_positive_idx)
        num_negative = (last_neg_idx) + 1

        return max(num_positive,num_negative)

As you can see the time complexity is O(logn) as we do two binary searches. There is a way to combine both in one pass but in terms of time complexity, it doesn’t matter. It has a space complexity of O(1) as we are not storing anything other than some variables which take up constant space.

Thanks for reading the article, let me know in the comments which problems you want me to either write the solution or create a youtube walkthrough in the comments.