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: We can iterate through the array while maintaining two counters: one for the length of the subarray when the product is positive (posCount) and another when it is negative (negCount). Each time we encounter a number, we adjust these counters based on whether the number is positive or negative.
When a zero is encountered, both counters are reset since any subarray including zero cannot yield a positive product. The aim is to keep track of the maximum posCount encountered, which indicates the maximum length of a subarray with a positive product.
This solution scans through the array and maintains two counts (posCount and negCount) to determine the maximum subarray length with a positive product. We update these counters based on whether the current number is positive, negative, or zero.
Time Complexity: O(n), where n is the number of elements in nums as we iterate through the array once.
Space Complexity: O(1), since we are using a constant amount of space.
Approach: We can approach the problem with a two-pass method, traversing the array twice: in the forward direction and reverse direction. During each traversal, we maintain counts of positive and negative products and update maximum lengths as required. This approach helps in scenarios where negative element pairs might yield positive results when considered in different subarrays formed during forward and backtracking.
This solution consists of two passes: a forward traversal followed by a backward traversal where we adjust positive and negative product counters. We track maximum subarray lengths in both directions to find the result.
Time Complexity: O(n), due to two separate linear traversals.
Space Complexity: O(1), as it uses a constant number of variables for tracking progress and computing the maximum length.
We define two arrays f and g of length n, where f[i] represents the length of the longest subarray ending at nums[i] with a positive product, and g[i] represents the length of the longest subarray ending at nums[i] with a negative product.
Initially, if nums[0] > 0, then f[0] = 1, otherwise f[0] = 0; if nums[0] < 0, then g[0] = 1, otherwise g[0] = 0. We initialize the answer ans = f[0].
Next, we iterate through the array nums starting from i = 1. For each i, we have the following cases:
nums[i] > 0, then f[i] can be transferred from f[i - 1], i.e., f[i] = f[i - 1] + 1, and the value of g[i] depends on whether g[i - 1] is 0. If g[i - 1] = 0, then g[i] = 0, otherwise g[i] = g[i - 1] + 1;nums[i] < 0, then the value of f[i] depends on whether g[i - 1] is 0. If g[i - 1] = 0, then f[i] = 0, otherwise f[i] = g[i - 1] + 1, and g[i] can be transferred from f[i - 1], i.e., g[i] = f[i - 1] + 1.ans = max(ans, f[i]).After the iteration, we return the answer ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
We observe that for each i, the values of f[i] and g[i] only depend on f[i - 1] and g[i - 1]. Therefore, we can use two variables f and g to record the values of f[i - 1] and g[i - 1], respectively, thus optimizing the space complexity to O(1).
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach With Signs | Time Complexity: O(n), where n is the number of elements in nums as we iterate through the array once. |
| Two-Pass Approach | Time Complexity: O(n), due to two separate linear traversals. |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
| 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. |
Leetcode 1567. Maximum Length of Subarray With Positive Product • Fraz • 17,904 views views
Watch 9 more video solutions →Practice Maximum Length of Subarray With Positive Product with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor