Watch 10 video solutions for Maximum Length of Subarray With Positive Product, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by Fraz has 17,904 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105-109 <= nums[i] <= 109Problem Overview: Given an integer array that may contain positive numbers, negative numbers, and zeros, determine the maximum length of a contiguous subarray whose product is positive. The challenge comes from sign changes: every negative value flips the sign of the product, while zero resets the product entirely.
Approach 1: Greedy Approach With Signs (O(n) time, O(1) space)
This method tracks two running lengths while iterating through the array: the length of the longest subarray ending at the current index with a positive product, and the length with a negative product. When you see a positive number, the positive length increases while the negative length extends only if it already exists. When a negative number appears, the two lengths swap because multiplying by a negative flips the sign. A zero resets both counters since any subarray containing zero has product zero. This greedy state-tracking behaves similarly to dynamic programming, but uses constant space and updates in a single pass. The result is the maximum positive length seen during iteration.
Approach 2: Two-Pass Approach (O(n) time, O(1) space)
This approach relies on counting negatives inside segments separated by zeros. A subarray has a positive product when the number of negative values inside it is even. First split the array into segments using zeros as boundaries. For each segment, count the positions of the first and last negative elements. If the segment has an even number of negatives, the entire segment works. If the count is odd, remove either the prefix up to the first negative or the suffix after the last negative and take the longer remaining subarray. Implementations often scan from left to right and then from right to left to handle both trimming options efficiently. This technique fits naturally with array traversal patterns and resembles a simplified greedy decision process.
Recommended for interviews: The greedy sign-tracking approach is typically expected. It shows that you understand how negative numbers affect product parity and how to maintain running state efficiently. The two-pass method is also acceptable and sometimes easier to reason about when explaining the logic around even and odd negative counts. Interviewers mainly look for an O(n) solution with constant space and correct handling of zeros.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Approach With Signs | O(n) | O(1) | Best general solution. Single pass with constant memory and clean sign tracking. |
| Two-Pass Approach | O(n) | O(1) | Useful when reasoning about negative counts in segments separated by zeros. |