2529. Maximum Count of Positive Integer and Negative Integer

EasyArrayBinary SearchCounting
Leetcode Link

Problem Description

In this problem, we are provided with a sorted array nums which is in non-decreasing order. Our task is to find the maximum count of either positive integers or negative integers present in the array. It is important to note that the number 0 is considered neither positive nor negative. We need to return the higher count between the total number of positive integers and the number of negative integers in the array.

Intuition

Since the array is sorted in non-decreasing order, all negative numbers, if any, will be positioned at the beginning of the array, followed by zeroes and then positive numbers. Identifying the number of positive numbers can be done by finding the first occurrence of a number greater than or equal to 1. The count of positive numbers is then the total length of the array minus the index of this first positive number. Similarly, the number of negative numbers is the index where the first non-negative number (which could be 0) is located, as this index is equal to the count of negative numbers before it.

We can efficiently find these points of transition from negative to zero and from zero to positive using a binary search technique. The Python bisect library offers functions like bisect_left which can be leveraged for this purpose:

  • bisect_left(nums, 1) will return the index of the first positive integer.
  • bisect_left(nums, 0) will give the index of the first non-negative integer, which is also the count of the negative integers.

Finally, we take the maximum between the count of positive numbers and negative numbers and return it as the solution. The use of binary search here allows the solution to be efficient even for large arrays.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What data structure does Breadth-first search typically uses to store intermediate states?

Solution Approach

The solution approach takes advantage of the sorted nature of the input array and binary search algorithm to efficiently find the count of negative and positive numbers. It uses the bisect library in Python, which provides a collection of tools for handling sorted lists.

Here's a step-by-step breakdown of how the algorithm works:

  1. Calculate the count of positive numbers by finding the index of the first positive integer. Since the array is sorted, all positive integers are at the end. The function bisect_left(nums, 1) finds the leftmost value greater than or equal to 1. This is essentially the index of the first positive number. The count of positive numbers is then the length of the array minus this index.

  2. Find the count of negative numbers by locating the index of the first non-negative integer (either 0 or the first positive). bisect_left(nums, 0) will give us this index directly, which represents the total number of negative integers since they are all to the left of this point in the sorted array.

  3. The max(a, b) function is then used to compare the counts of positive numbers (a) and negative numbers (b) and return the larger of the two. This maximum value represents the largest group, either positive or negative numbers within the array.

The code uses bisect_left twice on the sorted array, making the time complexity O(log n), where n is the size of the array nums. The space complexity is O(1) because we are only storing two integers for the counts and the result, using no additional space proportionate to the input size.

In essence, the implementation leverages binary search to pinpoint the transition points within the array—the first transition from negative to either zero or positive and the second transition from zero to positive—and then uses simple arithmetic and the max function to determine the answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's consider the following example array of sorted integers:

1nums = [-4, -3, -2, 0, 2, 3, 5]

In this example, we shall walk through the algorithm steps based on the solution approach.

  1. Find the count of positive numbers:

    • We want to locate the index of the first positive integer. Since the array is non-decaying, we can use bisect_left(nums, 1) to find this point efficiently.
    • Applying bisect_left(nums, 1) to our example, we identify that the first occurrence of a number greater than or equal to 1 is positioned at index 4 where the value is 2.
    • The count of positive integers is then the total array length 7 minus the index 4, which equals 3. So there are 3 positive numbers.

  2. Determine the count of negative numbers:

    • Here, we aim to locate the index of the first non-negative number (0 or a positive integer). bisect_left(nums, 0) will help find that index.
    • In our example, bisect_left(nums, 0) returns index 3 as the first location where the value 0 or a number greater does not precede it.
    • This indicates that there are precisely 3 negative integers before the zero found at index 3.

  3. Choose the maximum count:

    • We need to decide which group is larger: negative numbers or positive numbers. By using the max(a, b) function where a is the number of positives and b is the number of negatives, we can quickly infer the larger count.
    • Comparing 3 (positive count) and 3 (negative count), we see that they are equal. Therefore, the function should return 3.

With these steps, the algorithm determines that the maximum count of either positive or negative integers in the array nums is 3. The efficient use of binary search allows us to conclude without having to iterate over the entire array, thus maintaining a time complexity of O(log n).

Solution Implementation

1from bisect import bisect_left
2from typing import List
3
4class Solution:
5    def maximumCount(self, nums: List[int]) -> int:
6        # Calculate the number of elements equal or greater than 1 using binary search.
7        # bisect_left returns the leftmost place in the sorted list to insert the number 1
8        # Subtract this from the length of the array to find the count of elements >= 1
9        count_ones_or_more = len(nums) - bisect_left(nums, 1)
10
11        # Calculate the number of elements which are negative using binary search.
12        # bisect_left returns the leftmost place in the sorted list to insert number 0
13        # It gives us the number of negative numbers since the list is sorted.
14        count_negative = bisect_left(nums, 0)
15
16        # Return the maximum of the two counts calculated
17        return max(count_ones_or_more, count_negative)
18
1class Solution {
2
3    // Method calculates the maximum count of either 0's or 1's in a sorted binary array
4    public int maximumCount(int[] nums) {
5        // Find the number of 1's by subtracting the index of the first 1 from the array length
6        int countOfOnes = nums.length - firstOccurrence(nums, 1);
7        // Find the first occurrence index of 0, which is also the count of 0's
8        int countOfZeros = firstOccurrence(nums, 0);
9        // Return the max count between 0's and 1's
10        return Math.max(countOfOnes, countOfZeros);
11    }
12
13    // Helper method to find the first occurrence index of 'x' in the sorted array 'nums'
14    private int firstOccurrence(int[] nums, int x) {
15        int left = 0;
16        int right = nums.length;
17        // Binary search to find the first occurrence of 'x'
18        while (left < right) {
19            int mid = (left + right) >> 1; // Equivalent to (left + right) / 2 but faster
20            // If mid element is greater than or equal to x, we move the right boundary
21            if (nums[mid] >= x) {
22                right = mid;
23            } else {
24                // If mid element is less than x, we move the left boundary
25                left = mid + 1;
26            }
27        }
28        // 'left' will point to the first occurrence of 'x' or nums.length if 'x' is not found
29        return left;
30    }
31}
32
1// Include the necessary header files
2#include <vector>
3#include <algorithm> // Needed for std::lower_bound function
4
5class Solution {
6public:
7    // Function to find the maximum count of elements greater than or equal to 1
8    // or the number of elements before the first occurrence of 1 in the sorted array.
9    int maximumCount(std::vector<int>& nums) {
10        // Find the number of elements that are greater than or equal to 1.
11        // This is done by finding the lower bound of 1 in the array, 
12        // which gives an iterator to the first element not less than 1,
13        // and then calculating the distance from this iterator to the end of the array.
14        int countOfOnesOrGreater = nums.end() - std::lower_bound(nums.begin(), nums.end(), 1);
15
16        // Similar to the above, find the lower bound of 0, which is the first occurrence of 0,
17        // and then calculate the distance from the beginning of the array to this iterator.
18        // This is the number of elements that are less than 1.
19        int countBeforeFirstOne = std::lower_bound(nums.begin(), nums.end(), 0) - nums.begin();
20
21        // Return the maximum of the two counts calculated above.
22        return std::max(countOfOnesOrGreater, countBeforeFirstOne);
23    }
24};
25
1// Function that returns the maximum count of zeroes or ones by either 
2// counting the number of zeroes from the start or the number of ones from the end
3function maximumCount(nums: number[]): number {
4    // Helper function to perform a binary search for the target value (0 or 1)
5    // and return the index of the first occurrence of the target in the sorted array
6    const binarySearch = (target: number): number => {
7        let left = 0;    // Starting index of the search range
8        let right = nums.length; // Ending index of the search range (exclusive)
9
10        // While the search range is not empty
11        while (left < right) {
12            // Calculate the midpoint to divide the search range
13            const mid = (left + right) >>> 1; // Equivalent to Math.floor((left + right) / 2)
14          
15            // Narrow down the search range based on the comparison with target
16            if (nums[mid] < target) {
17                left = mid + 1; // Target must be in the upper half of the range
18            } else {
19                right = mid;    // Target is in the lower half or at the midpoint
20            }
21        }
22        // Return the final index where the target should be inserted
23        return left;
24    };
25
26    // Find the index of the first occurrence of 0 and 1 using binary search
27    const indexZero = binarySearch(0);
28    const indexOne = binarySearch(1);
29
30    // Calculate the maximum count of either zeroes or ones
31    // by choosing the higher count between the two
32    return Math.max(indexZero, nums.length - indexOne);
33}
34
Not Sure What to Study? Take the 2-min Quiz：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Time and Space Complexity

Time Complexity

The given code consists mainly of two binary searches, one to find the index of the first occurrence of 1 using bisect_left(nums, 1) and another one to find the index of the first occurrence of 0 using bisect_left(nums, 0). Since binary search has a time complexity of O(log n) for a list of n elements, and we are performing two binary searches, the overall time complexity of the function is O(log n).

Space Complexity

The implemented function does not create any additional data structures that grow with the input size. Thus, the space complexity is constant, O(1), regardless of the input size of nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫