Maximum Count of Positive Integer and Negative Integer

Easy

Asked by:

16 views

Topics:

ArraysBinary Search

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?

Try coding it in LeetCode

Maximum Count of Positive Integer and Negative Integer

Easy

Asked by:

16 views

Topics:

ArraysBinary Search

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?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values that can be present in the input array?
Can the input array be empty or null?
If the number of positive and negative integers are equal, which count should I return?
Are duplicate numbers allowed in the input array, and if so, how should they be counted?
Is the input array guaranteed to be sorted in any particular order?

Brute Force Solution

Approach

The brute force method to find the maximum count of positive and negative numbers involves simply counting all the positive and negative numbers individually. Then, we compare these two counts to determine which is bigger.

Here's how the algorithm would work step-by-step:

First, go through each number one at a time.
For each number, check if it's greater than zero. If it is, add one to the count of positive numbers.
If the number is not greater than zero, check if it is less than zero. If it is, add one to the count of negative numbers.
Once you've checked all the numbers, you'll have a total count of positive numbers and a total count of negative numbers.
Finally, compare the total positive count and the total negative count. The larger of these two numbers is your answer.

Code Implementation

def maximum_count_of_positive_integer_and_negative_integer(numbers):
    positive_count = 0
    negative_count = 0

    for number in numbers:
        # Count the number of positive integers
        if number > 0:

            positive_count += 1

        # Count the number of negative integers.
        elif number < 0:

            negative_count += 1

    # Determine which count is larger.
    if positive_count > negative_count:

        return positive_count

    else:
        return negative_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n elements in the input array nums exactly once. For each element, it performs a constant time comparison to check if the element is positive or negative, and increments the corresponding counter. Since we visit each element only once, the time complexity is directly proportional to the number of elements in the input array. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses only two integer variables to store the counts of positive and negative numbers. The space required for these variables remains constant regardless of the size of the input array. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks us to find whether there are more positive or negative numbers in a list. The fastest way is to count positive and negative numbers separately and then directly compare the counts.

Here's how the algorithm would work step-by-step:

Start by checking each number in the list one by one.
If the number is bigger than zero, add one to a counter for positive numbers.
If the number is smaller than zero, add one to a counter for negative numbers.
If the number is zero, don't change either counter.
After checking every number, compare the positive counter and the negative counter.
Return the bigger of the two counters. If they are the same, it does not matter which one you return.

Code Implementation

def maximum_count_of_positive_integer_and_negative_integer(numbers):
    positive_count = 0
    negative_count = 0

    for number in numbers:
        if number > 0:
            # Increment positive_count when we find a positive number.
            positive_count += 1

        elif number < 0:
            # Increment negative_count when we find a negative number.
            negative_count += 1

    # Comparing positive and negative counts to return the maximum.
    if positive_count > negative_count:
        return positive_count
    else:
        return negative_count

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input list nums of size n exactly once. Inside the loop, there are only constant-time operations: comparing the current number to zero and incrementing either the positive or negative counter. Therefore, the time complexity is directly proportional to the size of the input list. This results in a linear time complexity of O(n).

Space Complexity

O(1) – The provided solution uses two integer counters, one for positive numbers and one for negative numbers. The space required for these counters remains constant regardless of the size of the input list. Therefore, the auxiliary space complexity is O(1), indicating constant space usage independent of the input size N.

Edge Cases

Case	How to Handle
Empty input array	Return 0 since there are no positive or negative numbers to count.
Array containing only zeros	Return 0 since there are no positive or negative numbers.
Array containing only positive numbers	Return the length of the array as the positive count.
Array containing only negative numbers	Return the absolute value of the length of the array, as the negative count.
Array with extreme positive and negative values close to integer limits	The comparison logic should not cause integer overflow errors.
Array with a large number of duplicates of the same positive and negative values	The counting logic should accurately reflect the number of distinct positive and negative numbers.
Array with an equal number of positive and negative numbers	Return either the positive or negative count as they are equal; the solution should be deterministic.
Null input	Throw an IllegalArgumentException or return 0 based on requirements.