Leetcode 1567 - Maximum Length of Subarray With Positive Product

Table of Contents

Problem

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.

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.

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^5
• -10^9 <= nums[i] <= 10^9

Explanation/Approach

The key to solving this problem is to realize that a subarray’s product is positive if it contains an even number of negative numbers. Zeroes reset the subarray as they make the product zero. We will use dynamic programming to solve this problem.

Dynamic Programming Approach:

1. Track Positive and Negative Lengths: Keep track of the length of the subarray with a positive product (positiveLength) and the length of the subarray with a negative product (negativeLength).
2. Iterate Over the Array: For each element in the array:
   • If the element is positive, increment positiveLength. If negativeLength is not zero, increment it too.
   • If the element is negative, swap positiveLength and negativeLength and then increment negativeLength.
   • If the element is zero, reset both lengths to zero.
3. Update Maximum Length: After processing each element, update the maximum length of the subarray with a positive product.

Solution: Dynamic Programming

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        positiveLength, negativeLength = 0, 0
        maxLength = 0

        for num in nums:
            if num > 0:
                positiveLength += 1
                negativeLength = negativeLength + 1 if negativeLength > 0 else 0
            elif num < 0:
                positiveLength = negativeLength + 1 if negativeLength > 0 else 0
                negativeLength = positiveLength + 1
            else:
                positiveLength, negativeLength = 0, 0

            maxLength = max(maxLength, positiveLength)

        return maxLength

Time and Memory Complexity

• Time Complexity: O(n), where n is the length of nums. We iterate through the array once.
• Memory Complexity: O(1), as we only use a few variables for tracking lengths and do not use any additional data structures.

Visual Representation

Consider the input nums = [0,1,-2,-3,-4].

1. Iterate through the array:

   • Start with positiveLength = 0, negativeLength = 0.
   • For 1 (positive), positiveLength = 1, negativeLength = 0.
   • For -2 (negative), swap lengths, positiveLength = 0, negativeLength = 2.
   • For -3 (negative), swap lengths again, positiveLength = 3, negativeLength = 0.
   • For -4 (negative), swap lengths, positiveLength = 0, negativeLength = 4.

2. Maximum Length Update:

   • The maximum positiveLength observed is 3, which is the length of the subarray [1,-2,-3].