Jobs

Interviews

Discussions

Maximum Length of Subarray With Positive Product

Medium

Asked by:

2 views

Topics:

ArraysDynamic Programming

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Maximum Length of Subarray With Positive Product

Medium

Asked by:

2 views

Topics:

ArraysDynamic Programming

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

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 are the possible values in the array, and what is the maximum size of the input array?
Can the array contain zero? How should I handle cases where the entire array has a non-positive product?
If there are multiple subarrays with the maximum positive product length, can I return the length of any one of them?
Is the input array guaranteed to be valid (not null or empty)? If the input is invalid what should my code return?
By subarray, do you mean a contiguous sequence of elements?

Brute Force Solution

Approach

The brute force way to solve this is to look at every possible section of the list. For each section, we will determine if the product is positive, and if so, keep track of its length.

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

Start by considering the very first number in the list as a section by itself.
Then, consider the first two numbers together as a section, then the first three, and so on, all the way to the end of the list.
For each of these sections, multiply all the numbers within that section together.
If the result of the multiplication is a positive number, we remember the length of that section.
Next, do the same thing, but start with the *second* number in the list, and consider sections starting there.
Keep doing this, each time starting from a later number in the list, until you've considered every possible starting point.
Once you have considered every possible section of the list, look at all the lengths you remembered where the product was positive, and select the longest one.

Code Implementation

def get_max_len_positive_product(
    numbers
):
    max_length = 0

    # Iterate through all possible start indices
    for start_index in range(len(numbers)):
        # Iterate through all possible end indices
        for end_index in range(start_index, len(numbers)):
            current_product = 1

            # Calculate the product of the current subarray
            for index in range(start_index, end_index + 1):
                current_product *= numbers[index]

            # Check if the product is positive
            if current_product > 0:
                # Update max_length if necessary
                subarray_length = end_index - start_index + 1

                # Update maximum length found
                if subarray_length > max_length:
                    max_length = subarray_length

    return max_length

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible subarrays of the input array of size n. The outer loop iterates n times, defining the start of the subarray. The inner loop iterates up to n times, defining the end of the subarray. Inside the inner loop, the product of the subarray elements is calculated, which takes O(n) time in the worst case (when the subarray spans most of the array). Thus, the total time complexity is O(n * n * n), which simplifies to O(n³).

Space Complexity

O(1) – The provided brute force approach calculates the product for each subarray and remembers the length of the longest subarray with a positive product. It only needs to store a few scalar variables: loop counters for iterating through subarrays, a variable to hold the product of the current subarray, and a variable to store the maximum length found so far. The number of variables remains constant regardless of the input size N (the length of the input list). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find the longest section where multiplying all the numbers gives a positive result, we need to cleverly track how many positive and negative numbers we've seen so far. The core idea is to keep track of where the first negative number was encountered because an even number of negatives results in a positive product.

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

Start at the beginning and track the length of a section with a positive product.
Keep track of the position of the first negative number we see.
If we encounter a zero, the current section ends, so we reset our counts and start again.
If the number of negative numbers we've seen is even, then the entire section so far has a positive product, so we update the maximum length if the current section is longer.
If the number of negative numbers is odd, then we need to remove the impact of the first negative number encountered. We do this by considering only the section from just after the first negative number up to the current position. Then, we update the maximum length if this new section is longer.
By carefully keeping track of these two sections (from the start and after the first negative), we efficiently find the longest possible positive product without re-checking any sections multiple times.

Code Implementation

def find_max_positive_product_length(nums):
    maximum_length = 0
    start_index = -1
    first_negative_index = -1
    negative_count = 0

    for i, num in enumerate(nums):
        if num == 0:
            start_index = -1
            first_negative_index = -1
            negative_count = 0
            continue

        if start_index == -1:
            start_index = i

        if num < 0:
            negative_count += 1

            # Store the first negative index to handle odd negative counts.
            if first_negative_index == -1:
                first_negative_index = i

        # Even negative count means the whole subarray has a positive product.
        if negative_count % 2 == 0:
            maximum_length = max(maximum_length, i - start_index + 1)

        # Odd negative count means we exclude the subarray before the first negative.
        else:
            maximum_length = max(maximum_length, i - first_negative_index)

    return maximum_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n only once. During this iteration, it performs a fixed number of operations for each element: checking if the number is zero, negative, or positive; updating the count of negative numbers; and updating the maximum length based on whether the count of negative numbers is even or odd. Since the work done for each element is constant and independent of n, the overall time complexity is directly proportional to the input size n, thus resulting in O(n).

Space Complexity

O(1) – The provided algorithm uses a fixed number of variables to keep track of the current length, the first negative number's index, and the maximum length encountered. These variables consume a constant amount of memory regardless of the input array's size (N). No auxiliary data structures like arrays, lists, or hash maps that scale with the input are used. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0, as there is no subarray with a positive product.
Array with a single element (positive)	Return 1, as the single element forms a subarray of length 1 with a positive product.
Array with a single element (negative)	Return 0, as the single element forms a subarray of length 1 with a negative product.
Array containing only zeros	Return 0, as no subarray can have a positive product.
Array with alternating positive and negative numbers	The algorithm must correctly track the length of positive and negative subarrays, resetting when a zero is encountered.
Array with a large number of zeros	The algorithm should efficiently reset and restart subarray calculations at each zero encountered, preventing unnecessary computations.
Array with extreme negative numbers (potential for integer overflow with multiplication)	The problem statement likely constrains the range, or the test should handle potential overflow, but consider using a `long` data type if overflow is a concern with the given data type limits.
Array where all numbers are negative	The solution needs to track the first and last negative number indices to calculate the length of the longest positive product subarray formed by excluding either the first or last negative number.

Empty or null input array

How to Handle:

Return 0, as there is no subarray with a positive product.

Array with a single element (positive)

How to Handle:

Return 1, as the single element forms a subarray of length 1 with a positive product.

Array with a single element (negative)

How to Handle:

Return 0, as the single element forms a subarray of length 1 with a negative product.

Array containing only zeros

How to Handle:

Return 0, as no subarray can have a positive product.

Array with alternating positive and negative numbers

How to Handle:

The algorithm must correctly track the length of positive and negative subarrays, resetting when a zero is encountered.

Array with a large number of zeros

How to Handle:

The algorithm should efficiently reset and restart subarray calculations at each zero encountered, preventing unnecessary computations.

Array with extreme negative numbers (potential for integer overflow with multiplication)

How to Handle:

The problem statement likely constrains the range, or the test should handle potential overflow, but consider using a `long` data type if overflow is a concern with the given data type limits.

Array where all numbers are negative

How to Handle:

The solution needs to track the first and last negative number indices to calculate the length of the longest positive product subarray formed by excluding either the first or last negative number.

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 are the possible values in the array, and what is the maximum size of the input array?
Can the array contain zero? How should I handle cases where the entire array has a non-positive product?
If there are multiple subarrays with the maximum positive product length, can I return the length of any one of them?
Is the input array guaranteed to be valid (not null or empty)? If the input is invalid what should my code return?
By subarray, do you mean a contiguous sequence of elements?

Brute Force Solution

Approach

The brute force way to solve this is to look at every possible section of the list. For each section, we will determine if the product is positive, and if so, keep track of its length.

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

Start by considering the very first number in the list as a section by itself.
Then, consider the first two numbers together as a section, then the first three, and so on, all the way to the end of the list.
For each of these sections, multiply all the numbers within that section together.
If the result of the multiplication is a positive number, we remember the length of that section.
Next, do the same thing, but start with the *second* number in the list, and consider sections starting there.
Keep doing this, each time starting from a later number in the list, until you've considered every possible starting point.
Once you have considered every possible section of the list, look at all the lengths you remembered where the product was positive, and select the longest one.

Code Implementation

def get_max_len_positive_product(
    numbers
):
    max_length = 0

    # Iterate through all possible start indices
    for start_index in range(len(numbers)):
        # Iterate through all possible end indices
        for end_index in range(start_index, len(numbers)):
            current_product = 1

            # Calculate the product of the current subarray
            for index in range(start_index, end_index + 1):
                current_product *= numbers[index]

            # Check if the product is positive
            if current_product > 0:
                # Update max_length if necessary
                subarray_length = end_index - start_index + 1

                # Update maximum length found
                if subarray_length > max_length:
                    max_length = subarray_length

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the beginning and track the length of a section with a positive product.
Keep track of the position of the first negative number we see.
If we encounter a zero, the current section ends, so we reset our counts and start again.
If the number of negative numbers we've seen is even, then the entire section so far has a positive product, so we update the maximum length if the current section is longer.
If the number of negative numbers is odd, then we need to remove the impact of the first negative number encountered. We do this by considering only the section from just after the first negative number up to the current position. Then, we update the maximum length if this new section is longer.
By carefully keeping track of these two sections (from the start and after the first negative), we efficiently find the longest possible positive product without re-checking any sections multiple times.

Code Implementation

def find_max_positive_product_length(nums):
    maximum_length = 0
    start_index = -1
    first_negative_index = -1
    negative_count = 0

    for i, num in enumerate(nums):
        if num == 0:
            start_index = -1
            first_negative_index = -1
            negative_count = 0
            continue

        if start_index == -1:
            start_index = i

        if num < 0:
            negative_count += 1

            # Store the first negative index to handle odd negative counts.
            if first_negative_index == -1:
                first_negative_index = i

        # Even negative count means the whole subarray has a positive product.
        if negative_count % 2 == 0:
            maximum_length = max(maximum_length, i - start_index + 1)

        # Odd negative count means we exclude the subarray before the first negative.
        else:
            maximum_length = max(maximum_length, i - first_negative_index)

    return maximum_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0, as there is no subarray with a positive product.
Array with a single element (positive)	Return 1, as the single element forms a subarray of length 1 with a positive product.
Array with a single element (negative)	Return 0, as the single element forms a subarray of length 1 with a negative product.
Array containing only zeros	Return 0, as no subarray can have a positive product.
Array with alternating positive and negative numbers	The algorithm must correctly track the length of positive and negative subarrays, resetting when a zero is encountered.
Array with a large number of zeros	The algorithm should efficiently reset and restart subarray calculations at each zero encountered, preventing unnecessary computations.
Array with extreme negative numbers (potential for integer overflow with multiplication)	The problem statement likely constrains the range, or the test should handle potential overflow, but consider using a `long` data type if overflow is a concern with the given data type limits.
Array where all numbers are negative	The solution needs to track the first and last negative number indices to calculate the length of the longest positive product subarray formed by excluding either the first or last negative number.

Empty or null input array

How to Handle:

Return 0, as there is no subarray with a positive product.

Array with a single element (positive)

How to Handle:

Return 1, as the single element forms a subarray of length 1 with a positive product.

Array with a single element (negative)

How to Handle:

Return 0, as the single element forms a subarray of length 1 with a negative product.

Array containing only zeros

How to Handle:

Return 0, as no subarray can have a positive product.

Array with alternating positive and negative numbers

How to Handle:

The algorithm must correctly track the length of positive and negative subarrays, resetting when a zero is encountered.

Array with a large number of zeros

How to Handle:

The algorithm should efficiently reset and restart subarray calculations at each zero encountered, preventing unnecessary computations.

Array with extreme negative numbers (potential for integer overflow with multiplication)

How to Handle:

The problem statement likely constrains the range, or the test should handle potential overflow, but consider using a `long` data type if overflow is a concern with the given data type limits.

Array where all numbers are negative

How to Handle:

The solution needs to track the first and last negative number indices to calculate the length of the longest positive product subarray formed by excluding either the first or last negative number.