Taro Logo

Maximum Length of Subarray With Positive Product

Medium
Amazon logo
Amazon
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.

For example:

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

  2. 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.

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

What is the most efficient algorithm to solve this problem? Consider edge cases and explain the time and space complexity.

Solution


Naive Approach

A brute-force solution would involve iterating through all possible subarrays and checking if the product of each subarray is positive. We would keep track of the maximum length of such a subarray.

def max_len_brute_force(nums):
    max_length = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            product = 1
            for k in range(i, j + 1):
                product *= nums[k]
            if product > 0:
                max_length = max(max_length, j - i + 1)
    return max_length

Time Complexity: O(n^3), where n is the length of the input array nums. This is because we have nested loops to iterate through all possible subarrays, and another inner loop to calculate the product of each subarray.

Space Complexity: O(1), as we are only using a constant amount of extra space.

Optimal Approach

A more efficient solution involves using dynamic programming. We can keep track of the maximum length of positive and negative product subarrays ending at each index. Let pos[i] be the maximum length of a positive product subarray ending at index i, and neg[i] be the maximum length of a negative product subarray ending at index i.

  1. If nums[i] > 0, then pos[i] = pos[i-1] + 1 and neg[i] = neg[i-1] + 1 if neg[i-1] > 0, otherwise neg[i] = 0.
  2. If nums[i] < 0, then pos[i] = neg[i-1] + 1 if neg[i-1] > 0, otherwise pos[i] = 0, and neg[i] = pos[i-1] + 1.
  3. If nums[i] == 0, then pos[i] = 0 and neg[i] = 0.

We can optimize space by just using two variables to store the current positive and negative lengths instead of arrays.

def get_max_len(nums):
    pos = 0
    neg = 0
    max_length = 0

    for num in nums:
        if num > 0:
            pos += 1
            neg = neg + 1 if neg > 0 else 0
        elif num < 0:
            new_pos = neg + 1 if neg > 0 else 0
            new_neg = pos + 1
            pos = new_pos
            neg = new_neg
        else:
            pos = 0
            neg = 0
        max_length = max(max_length, pos)

    return max_length

Time Complexity: O(n), where n is the length of the input array nums. We iterate through the array only once.

Space Complexity: O(1), as we are only using a constant amount of extra space.

Edge Cases

  • Empty array: Should return 0.
  • Array with all zeros: Should return 0.
  • Array with a mix of positive, negative, and zero values.
  • Array with all positive values: Should return the length of the array.
  • Array with all negative values: Should return 0 if the length is even, and 1 if the length is odd.