LeetCode 1567 - Maximum Length of Subarray With Positive Product

The problem asks us to find the length of the longest contiguous subarray whose product of elements is strictly positive. We are given an integer array nums, which may contain positive numbers, negative numbers, and zeros.

leetcodemediumarraydynamic-programminggreedy

LeetCode Problem 1567

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem asks us to find the length of the longest contiguous subarray whose product of elements is strictly positive.

We are given an integer array nums, which may contain positive numbers, negative numbers, and zeros. A subarray must consist of consecutive elements from the original array. Among all possible subarrays, we need to determine the maximum length where multiplying every element together produces a positive value.

The key observation is that the exact product value does not matter. We only care whether the product is positive or negative. This significantly simplifies the problem because the sign of a product depends entirely on the number of negative values:

  • An even number of negative numbers produces a positive product.
  • An odd number of negative numbers produces a negative product.
  • Any subarray containing 0 has product 0, which is not positive.

The constraints are important:

  • nums.length can be as large as 10^5
  • Values themselves can be large, up to 10^9 in magnitude

Because the array can contain one hundred thousand elements, any solution slower than linear or near-linear time will likely time out. Also, directly computing products is unnecessary and potentially dangerous because multiplication could overflow in some languages. Since only the sign matters, we should track positivity and negativity instead of actual product values.

Several edge cases are important:

  • Arrays containing many zeros, because zeros split the array into independent segments
  • Arrays containing only negative numbers
  • Arrays where the best answer appears in the middle
  • Arrays with alternating signs
  • Single-element arrays, especially [0], [1], and [-1]

A naive implementation that repeatedly computes products for every subarray would be far too slow.

Approaches

Brute Force Approach

The brute force solution checks every possible subarray. For each starting index, we extend the subarray one element at a time and compute whether the product is positive.

There are O(n^2) possible subarrays. If we explicitly multiply values for every subarray, the complexity becomes even worse. Even if we optimize by tracking only the sign, we still must inspect all subarrays.

The brute force method is correct because it exhaustively evaluates every candidate subarray and records the maximum valid length. However, with n = 10^5, an O(n^2) solution is far too slow.

Optimal Dynamic Programming / Greedy Observation

The important insight is that at every position, we only need to know:

  • The length of the longest subarray ending at this index with positive product
  • The length of the longest subarray ending at this index with negative product

We can process the array from left to right.

For each number:

  • A positive number preserves signs
  • A negative number flips signs
  • Zero resets everything

This leads to a very compact dynamic programming approach using only two variables.

If:

  • positive_len = longest positive-product subarray ending here
  • negative_len = longest negative-product subarray ending here

Then we can update these values in constant time for each element.

This gives a linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every possible subarray
Optimal O(n) O(1) Tracks positive and negative subarray lengths dynamically

Algorithm Walkthrough

  1. Initialize three variables:
  • positive_len = 0
  • negative_len = 0
  • max_length = 0

positive_len represents the longest subarray ending at the current index with positive product. negative_len represents the longest subarray ending at the current index with negative product. 2. Iterate through every number in the array from left to right. 3. If the current number is positive:

  • Any existing positive-product subarray remains positive after appending this number.
  • Any existing negative-product subarray remains negative after appending this number.

Therefore:

  • positive_len += 1
  • negative_len = negative_len + 1 if negative_len > 0
  1. If the current number is negative:
  • Appending a negative number flips the sign.
  • A previous positive-product subarray becomes negative.
  • A previous negative-product subarray becomes positive.

Since both values depend on previous states, store them temporarily before updating.

Then:

  • positive_len = previous_negative_len + 1 if previous negative exists
  • negative_len = previous_positive_len + 1
  1. If the current number is zero:
  • Any subarray containing zero has product zero.
  • No valid subarray can continue across zero.

Reset:

  • positive_len = 0
  • negative_len = 0
  1. After processing each element, update:
  • max_length = max(max_length, positive_len)
  1. After the loop finishes, return max_length.

Why it works

At every index, the algorithm maintains the exact lengths of the longest positive-product and negative-product subarrays ending at that position. These values fully capture all necessary information about previous elements because the sign of a product depends only on the parity of negative numbers. Since every update correctly transforms previous states based on the sign of the current number, the algorithm always maintains correct subproblem solutions and ultimately finds the global maximum.

Python Solution

from typing import List

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        positive_len = 0
        negative_len = 0
        max_length = 0

        for num in nums:
            if num > 0:
                positive_len += 1

                if negative_len > 0:
                    negative_len += 1

            elif num < 0:
                previous_positive = positive_len
                previous_negative = negative_len

                if previous_negative > 0:
                    positive_len = previous_negative + 1
                else:
                    positive_len = 0

                negative_len = previous_positive + 1

            else:
                positive_len = 0
                negative_len = 0

            max_length = max(max_length, positive_len)

        return max_length

The implementation directly follows the algorithm described earlier.

The variables positive_len and negative_len store the dynamic programming states for the current position. Instead of using arrays, we only keep the most recent values because each update depends only on the previous index.

When processing a positive number, signs do not change. Positive sequences grow longer, and negative sequences also extend if they already exist.

When processing a negative number, the signs flip. Because both values depend on previous states, temporary variables are used to avoid overwriting information before both updates are complete.

When encountering zero, both states reset because no subarray containing zero can have positive product.

The variable max_length continuously tracks the best positive-product subarray found so far.

Go Solution

func getMaxLen(nums []int) int {
    positiveLen := 0
    negativeLen := 0
    maxLength := 0

    for _, num := range nums {
        if num > 0 {
            positiveLen++

            if negativeLen > 0 {
                negativeLen++
            }

        } else if num < 0 {
            previousPositive := positiveLen
            previousNegative := negativeLen

            if previousNegative > 0 {
                positiveLen = previousNegative + 1
            } else {
                positiveLen = 0
            }

            negativeLen = previousPositive + 1

        } else {
            positiveLen = 0
            negativeLen = 0
        }

        if positiveLen > maxLength {
            maxLength = positiveLen
        }
    }

    return maxLength
}

The Go implementation mirrors the Python logic closely.

Go uses explicit integer variables instead of Python's dynamically typed integers. Integer overflow is not a concern because we never compute actual products, only lengths.

The function operates directly on slices, which are efficient references to arrays. Since the algorithm uses constant extra space, no additional allocations are needed.

Worked Examples

Example 1

Input:

nums = [1, -2, -3, 4]
Index Value positive_len negative_len max_length
0 1 1 0 1
1 -2 0 2 1
2 -3 3 1 3
3 4 4 2 4

Final answer:

4

The entire array has positive product because there are two negative numbers.

Example 2

Input:

nums = [0, 1, -2, -3, -4]
Index Value positive_len negative_len max_length
0 0 0 0 0
1 1 1 0 1
2 -2 0 2 1
3 -3 3 1 3
4 -4 2 4 3

Final answer:

3

The best subarray is [1, -2, -3].

Example 3

Input:

nums = [-1, -2, -3, 0, 1]
Index Value positive_len negative_len max_length
0 -1 0 1 0
1 -2 2 1 2
2 -3 2 3 2
3 0 0 0 2
4 1 1 0 2

Final answer:

2

The longest valid subarrays are [-1, -2] and [-2, -3].

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed exactly once
Space O(1) Only a few variables are maintained

The algorithm scans the array one time from left to right. Every update takes constant time, so the total runtime grows linearly with the input size.

No auxiliary arrays, stacks, or hash maps are needed. The solution only stores a handful of integers, giving constant extra space usage.

Test Cases

from typing import List

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        positive_len = 0
        negative_len = 0
        max_length = 0

        for num in nums:
            if num > 0:
                positive_len += 1

                if negative_len > 0:
                    negative_len += 1

            elif num < 0:
                previous_positive = positive_len
                previous_negative = negative_len

                if previous_negative > 0:
                    positive_len = previous_negative + 1
                else:
                    positive_len = 0

                negative_len = previous_positive + 1

            else:
                positive_len = 0
                negative_len = 0

            max_length = max(max_length, positive_len)

        return max_length

solution = Solution()

assert solution.getMaxLen([1, -2, -3, 4]) == 4  # entire array positive
assert solution.getMaxLen([0, 1, -2, -3, -4]) == 3  # zero splits segments
assert solution.getMaxLen([-1, -2, -3, 0, 1]) == 2  # best before zero

assert solution.getMaxLen([1]) == 1  # single positive
assert solution.getMaxLen([-1]) == 0  # single negative
assert solution.getMaxLen([0]) == 0  # single zero

assert solution.getMaxLen([1, 2, 3, 4]) == 4  # all positive
assert solution.getMaxLen([-1, -2, -3, -4]) == 4  # even negatives
assert solution.getMaxLen([-1, -2, -3]) == 2  # odd negatives

assert solution.getMaxLen([0, 0, 0]) == 0  # all zeros
assert solution.getMaxLen([1, 0, 1, 0, 1]) == 1  # separated positives

assert solution.getMaxLen([-1, 2]) == 1  # single positive subarray
assert solution.getMaxLen([2, -1, 2, -1, 2]) == 5  # alternating signs
assert solution.getMaxLen([-1, 2, -3, 4, -5, 6]) == 5  # mixed signs

assert solution.getMaxLen([1, -2, 3, -4, 5, -6]) == 5  # multiple sign flips
Test Why
[1, -2, -3, 4] Entire array has positive product
[0, 1, -2, -3, -4] Tests reset behavior after zero
[-1, -2, -3, 0, 1] Best subarray appears before zero
[1] Single positive element
[-1] Single negative element
[0] Single zero element
[1, 2, 3, 4] All positives
[-1, -2, -3, -4] Even number of negatives
[-1, -2, -3] Odd number of negatives
[0, 0, 0] Multiple zero resets
[1, 0, 1, 0, 1] Independent positive segments
[-1, 2] Best answer is a single positive element
[2, -1, 2, -1, 2] Alternating sign transitions
[-1, 2, -3, 4, -5, 6] Multiple flips between positive and negative
[1, -2, 3, -4, 5, -6] Long mixed-sign traversal

Edge Cases

One important edge case is arrays containing zeros. Since any product involving zero becomes zero, valid subarrays cannot cross a zero. A common bug is forgetting to fully reset state variables after encountering zero. This implementation correctly resets both positive_len and negative_len to zero whenever a zero appears.

Another important case is arrays with an odd number of negative values. For example, [-1, -2, -3] has overall negative product, but smaller subarrays may still have positive product. A naive approach that only checks total parity for the entire segment would fail. The dynamic programming approach continuously tracks both positive and negative states, so it correctly identifies the best valid subarray.

A third edge case involves a negative number appearing when no previous negative-product subarray exists. In this situation, a new positive-product subarray cannot be formed immediately. The implementation carefully checks whether previous_negative > 0 before extending into a positive state. Without this condition, the algorithm could incorrectly create nonexistent subarrays.

A fourth subtle case is single-element arrays. Arrays like [1], [-1], and [0] test whether initialization and updates work correctly when the array length is minimal. The algorithm handles these naturally because the state transitions are valid even for one iteration.