medium Maximum Length of Subarray With Positive Product

Problem Statement

Given an integer array nums, find the maximum length of a subarray where the product of all its elements is greater than 0.

A subarray is a sequence of consecutive elements from the original array.

Examples

Example 1:
- Input: nums = [1, -2, 3, 4]
- Expected Output: 2
- Justification: The longest subarray with a positive product is [3, 4], with a length of 2.
Example 2:
- Input: nums = [-1, -2, -3, -4]
- Expected Output: 4
- Justification: The entire array produces a positive product since an even number of negative numbers multiply to a positive product. Hence, the longest length is 4.
Example 3:
- Input: nums = [0, -1, 2, -3, 4, -5, 6]
- Expected Output: 5
- Justification: The longest subarray with a positive product is [2, -3, 4, -5, 6], with a length of 5.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Maximum Length of Subarray With Positive Product (medium)

1. Why / judgment

Product positive iff even number of negatives and no zeros. Zeros hard-split the array into independent segments. In a zero-free segment: if even negatives, whole length; if odd, drop prefix through first negative or suffix through last negative, take max remaining length. When-NOT: max product value -> Kadane-like dual max/min product DP (different problem).

2. Big-O derivation (K11)

O(n) one pass / O(1)
[1,-2,3,4]->2 ([3,4]); [-1,-2,-3,-4]->4 even negs
Zeros reset segment

3. Pattern + when-NOT (K12)

Name: SIGN PARITY SEGMENTS (ZERO SPLITS)

Recognition: longest contiguous subarray with product >0.

When-NOT: Max product value -> DP max/min. Count such subarrays -> different. Non-contiguous -> subset product different.

4. Edge hand-run (K13)

single 0 -> 0
single positive -> 1
single negative -> 0
empty segment after split

5. Interviewer follow-ups (model answers)

Q1. Why drop first or last neg when odd count?
A: Removes exactly one neg to make even; maximal keep is max of the two options.

Q2. Zeros inside?
A: Product 0 not >0; cannot include zeros.

Q3. Overflow product?
A: Track signs/counts only — never multiply large values.

6. Short drills

Drill: [0,1,-2,-3,0]->2
Drill: [1,-1,1] length options
Drill: all positives length n

✅ Solution Maximum Length of Subarray With Positive Product

Problem Statement

Given an integer array nums, find the maximum length of a subarray where the product of all its elements is greater than 0.

A subarray is a sequence of consecutive elements from the original array.

Examples

Example 1:
- Input: nums = [1, -2, 3, 4]
- Expected Output: 2
- Justification: The longest subarray with a positive product is [3, 4], with a length of 2.
Example 2:
- Input: nums = [-1, -2, -3, -4]
- Expected Output: 4
- Justification: The entire array produces a positive product since an even number of negative numbers multiply to a positive product. Hence, the longest length is 4.
Example 3:
- Input: nums = [0, -1, 2, -3, 4, -5, 6]
- Expected Output: 5
- Justification: The longest subarray with a positive product is [2, -3, 4, -5, 6], with a length of 5.

Solution

To solve this problem, we maintain a length of the longest subarray while traversing through the array once. Our approach relies on understanding how the sign of the product changes with each element. Specifically, a positive number doesn't change the product's sign, a negative number flips it, and zero resets it. Hence, we track the length of the subarray until the current position that leads to a positive and negative product separately, updating them based on the current number's sign.

This method is effective because it simplifies the problem to tracking the sign changes due to negative numbers and resets caused by zeros, which can be done in a single pass through the array. By keeping track of the lengths of subarrays that lead to both positive and negative products, we can efficiently find the maximum length of the subarray with a positive product without needing to calculate the actual products or examine every possible subarray explicitly.

Step-by-Step Algorithm

Initialize two counters: positiveCount to 0 and negativeCount to 0. These track the length of the longest subarray ending at the current index with a positive and negative product, respectively.
Initialize maxLength to 0 to keep track of the maximum length of subarrays with positive products.
Iterate through the array nums:
- If the current element is positive, increment positiveCount by 1. If negativeCount is not 0, increment it by 1 as well, since a negative product can become positive if multiplied by a negative number.
- If the current element is negative, swap positiveCount + 1 and negativeCount if value of negativeCount is 0. Otherwise, swap positiveCount + 1 and negativeCount + 1.
- If the current element is zero, reset both positiveCount and negativeCount to 0 since the product of any subarray containing zero is zero.
- Update maxLength with the maximum value between itself and positiveCount.
The answer is the value of maxLength after iterating through the entire array.

Algorithm Walkthrough

Let's consider the input [0, -1, 2, -3, 4, -5, 6].

Initialization:
- positiveCount = 0: Tracks the length of the current subarray with a positive product.
- negativeCount = 0: Tracks the length of the current subarray with a negative product.
- maxLength = 0: Keeps track of the maximum length of any subarray encountered with a positive product.
First Element (0):
- The first element is 0, which resets both positiveCount and negativeCount to 0.
- positiveCount = 0, negativeCount = 0.
- maxLength remains 0.
Second Element (-1):
- The second element is -1, a negative number.
- Swap positiveCount and negativeCount (both are 0 at this point, so swapping has no effect).
- Increment negativeCount by 1: negativeCount = 1.
- positiveCount remains 0.
- maxLength remains 0 (since there's no positive product subarray yet).
Third Element (2):
- The third element is 2, a positive number.
- Increment positiveCount (since it's positive): positiveCount = 1.
- Increment negativeCount (since a negative subarray exists): negativeCount = 2.
- Update maxLength to 1.
Fourth Element (-3):
- The fourth element is -3, a negative number.
- Swap positiveCount + 1 and negativeCount + 1 then increment negativeCount: positiveCount becomes 3 and negativeCount becomes 2.
- Increment negativeCount by 1: negativeCount = 2.
- Update maxLength to 2 (the length of subarray leading up to the second element).
Fifth Element (4):
- The fifth element is 4, a positive number.
- Increment positiveCount: positiveCount = 4.
- Increment negativeCount (since a negative subarray exists): negativeCount = 3.
- Update maxLength to 4.
Sixth Element (-5):
- The sixth element is -5, a negative number.
- Swap positiveCount + 1 and negativeCount + 1 then increment negativeCount: positiveCount becomes 4 and negativeCount becomes 5.
- Increment negativeCount by 1: negativeCount = 5.
- maxLength remains 4.
Seventh Element (6):
- The seventh element is 6, a positive number.
- Increment positiveCount: positiveCount = 5.
- Increment negativeCount (since a negative subarray exists): negativeCount = 6.
- Update maxLength to 5.
Final Output:
- After processing all elements, the maxLength found is 5.

Code

java

public class Solution {

  public int getMaxLen(int[] nums) {
    int positiveCount = 0, negativeCount = 0, maxLength = 0;
    for (int num : nums) {
      if (num > 0) {
        // Positive number found
        positiveCount++; // Increase length of subarray with positive product
        negativeCount = negativeCount == 0 ? 0 : negativeCount + 1; // Increase only if there's already a negative product
      } else if (num < 0) {
        // Negative number found
        int temp = positiveCount;
        positiveCount = negativeCount == 0 ? 0 : negativeCount + 1; // Swap counts, increase positiveCount if negativeCount was non-zero
        negativeCount = temp + 1; // Increase negativeCount
      } else {
        // Zero found, reset counts
        positiveCount = 0;
        negativeCount = 0;
      }
      maxLength = Math.max(maxLength, positiveCount); // Update maxLength
    }
    return maxLength;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the algorithm with new examples
    System.out.println(solution.getMaxLen(new int[] { 1, -2, 3, 4 })); // Expected Output: 2
    System.out.println(solution.getMaxLen(new int[] { -1, -2, -3, -4 })); // Expected Output: 4
    System.out.println(
      solution.getMaxLen(new int[] { 0, -1, 2, -3, 4, -5, 6 })
    ); // Expected Output: 5
  }
}

Complexity Analysis

Time Complexity: where n is the number of elements in the array. This is because the algorithm iterates through the array exactly once, performing a constant amount of work for each element.
Space Complexity: as the space required does not grow with the size of the input array. Only a fixed number of variables are used, regardless of the array size.

🎯 STRICT STANDOUT — Solution Maximum Length of Subarray With Positive Product

1. Why / judgment

Iterate; on zero flush segment stats (len, neg count, first/last neg index). For segment: if negCount even ans=max(len); else ans=max(len-firstNeg-1, lastNeg). Hand-run [1,-2,3,4]: segment len4, one neg at1 -> max(2,1)=2 -> [3,4]. [-1,-2,-3,-4] four negs even -> 4.

2. Big-O derivation (K11)

O(n)/O(1)
No multiply overflow
Multiple zeros consecutive empty segments

3. Pattern + when-NOT (K12)

Name: SEGMENT SIGN PARITY

Recognition: max length positive product subarray.

When-NOT: Max product value different DP.

4. Edge hand-run (K13)

leading trailing zeros
neg at ends only

5. Interviewer follow-ups (model answers)

Q1. firstNeg index relative?
A: Store index within segment or absolute with base.

Q2. Product zero?
A: Excluded by split.

Q3. All zeros?
A: ans 0.

6. Short drills

Drill: [1,-1,1,-1] even ->4
Drill: [1,-1,1] odd ->2
Drill: implement flush helper

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Maximum Length of Subarray With Positive Product? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Maximum Length of Subarray With Positive Product** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Maximum Length of Subarray With Positive Product** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Maximum Length of Subarray With Positive Product**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Maximum Length of Subarray With Positive Product**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Binary Tree Vertical Order Travers Gray Code →