We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Length of Subarray With Positive Product

Number: 1690

Difficulty: Medium

Paid? No

Companies: Amazon, Arcesium

Problem Description

Given an array of integers nums, find the maximum length of a subarray (a contiguous part of the array) for which the product of its elements is positive. Note that zeros break the subarray since any subarray containing zero has a product of zero.

Key Insights

  • A subarray will have a positive product if it has an even number of negative numbers.
  • Zeros split the array into segments, and each segment without zeros can be processed independently.
  • For each segment without zeros:
    • If the total negatives are even, the whole segment is valid.
    • If the negatives are odd, by removing either the portion before the first negative number or the portion after the last negative number, you can potentially form a valid subarray.
  • A linear pass can be used to determine the maximum length by tracking the start of the segment, the first negative index, and the count of negatives.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution iterates through the array and keeps track of segments defined by zeros. When processing a segment without zeros, it counts the number of negative numbers and notes the index of the first negative number. If the count of negatives is even, the entire segment forms a positive product. If odd, dropping the portion up to the first negative (or after the last negative) will yield a valid subarray. The algorithm updates the maximum length found during this process.

Code Solutions

# Python solution with detailed comments

def getMaxLen(nums):
    max_length = 0
    start = 0  # Beginning of current segment after last zero
    first_negative = -1  # Index of first negative number in the current segment
    negative_count = 0  # Count of negative numbers in the current segment

    for i, num in enumerate(nums):
        if num == 0:
            # Zero encountered, reset for next segment
            start = i + 1
            first_negative = -1
            negative_count = 0
        else:
            if num < 0:
                negative_count += 1
                if first_negative == -1:
                    first_negative = i  # record the index of the first negative
            # If even count of negatives, subarray from start to i is valid
            if negative_count % 2 == 0:
                max_length = max(max_length, i - start + 1)
            else:
                # Remove prefix up to the first negative to potentially get even negatives
                max_length = max(max_length, i - first_negative)
    return max_length

# Example usage:
print(getMaxLen([1,-2,-3,4]))  # Expected output: 4
← Back to All Questions