Log inSign up
mediumLeetCodeNot Started

Maximum Length of Subarray With Positive Product

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Single Negative Number:

Input: nums = [1, -2, -3, 4]
Output: 4
Explanation: The product of the whole array [1, -2, -3, 4] is 24 (positive), so length is 4.

Example 2 · Zero Separators:

Input: nums = [0, 1, -2, -3, -4]
Output: 3
Explanation: The longest subarray with positive product is [1, -2, -3] which has length 3 and product 6.

Example 3 · All Negative Odd Count:

Input: nums = [-1, -2, -3, 0, 1]
Output: 2
Explanation: Subarray [-1, -2] or [-2, -3] has positive product 2 or 6, length is 2.

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sign multiplication rules (+ * + = +, + * - = -, - * - = +)
  • Kadane's algorithm / Maximum Product Subarray
  • State transitions with zeroes as segment delimiters

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the dual-state (positive / negative) dynamic programming pattern for products.
  • Correctly reset states upon encountering 0.
  • Handle the sign swap on negative multiplication.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Maintain running posLen and negLen.
  • If nums[i] > 0 -> posLen++, negLen = (negLen > 0 ? negLen + 1 : 0).
  • If nums[i] < 0 -> newPos = (negLen > 0 ? negLen + 1 : 0), newNeg = posLen + 1, assign.
  • If nums[i] == 0 -> posLen = 0, negLen = 0.
  • maxLen = max(maxLen, posLen).

Connected Patterns:

Maximum Product SubarrayKadane's AlgorithmBest Time to Buy and Sell Stock with State Machine

1. Nested Loops Product Evaluation (Brute Force)

Intuition

Iterate over all possible starting positions i from 0 to n-1. For each i, expand j from i to n-1 maintaining the count of negative numbers and checking for zeros. If any element is 0, the product becomes 0. If the negative count is even (and positive count > 0), product is positive; update maxLen.

When to apply: Use to understand the sign multiplication rules before optimizing with dynamic programming.

All Subarrays Sign Tracking (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Single positive element qualifies
Visual state
Values and pointers at this exact step
pointers
S
1
-2
-3
4
0
↑ i=j=0
1
2
3
Variables at this step
start
0
end
0
sign
+
maxLen
1
Check / comparison
Subarray [0..0]: prod = 1 > 0
Decision / next transition
Positive product! Length = 1. Set maxLen = 1.
Why this step matters

Single positive element qualifies.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int getMaxLen(int[] nums) {
4 int n = nums.length;
5 int maxLen = 0;
6 for (int i = 0; i < n; i++) {
7 int negCount = 0;
8 for (int j = i; j < n; j++) {
9 if (nums[j] == 0) break;
10 if (nums[j] < 0) negCount++;
11 if (negCount % 2 == 0) {
12 maxLen = Math.max(maxLen, j - i + 1);
13 }
14 }
15 }
16 return maxLen;
17 }
18 }
19
20 public static void main(String[] args) {
21 Solution sol = new Solution();
22 int[] nums = {1, -2, -3, 4};
23 System.out.println("Max Length: " + sol.getMaxLen(nums));
24 }
25}

Time & Space Complexity

  • Time complexity: O(n^2) — Two nested loops checking all subarrays takes O(n2) iterations.
  • Space complexity: O(1) — Only constant extra variables are needed.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Zero-Separated Segment Analysis (Better)

Intuition

Zeros partition the array into independent segments. In any zero-free segment: 1. If negative count is even, product of entire segment is positive. 2. If negative count is odd, remove either the prefix ending at the first negative, or the suffix starting at the last negative. The maximum of these two options is the longest positive subarray in that segment.

When to apply: Use to understand the structural properties of negative parity in positive product intervals.

Zero-Segment Negative Count Boundary Scan (O(N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
When negative count is even, the product of the entire segment is strictly positive
Visual state
Values and pointers at this exact step
pointers
S
1
-2
-3
4
0
↑ scan
1
2
3
Variables at this step
zeros
0
negativeCount
2
isEven
true
Check / comparison
Scan segment: no zeros. Negative numbers are at index 1 (-2) and index 2 (-3)
Decision / next transition
Total negative count in segment = 2 (even number).
Why this step matters

When negative count is even, the product of the entire segment is strictly positive.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int getMaxLen(int[] nums) {
4 int maxLen = 0, n = nums.length;
5 int i = 0;
6 while (i < n) {
7 while (i < n && nums[i] == 0) i++;
8 if (i == n) break;
9 int start = i, firstNeg = -1, lastNeg = -1, negCount = 0;
10 while (i < n && nums[i] != 0) {
11 if (nums[i] < 0) {
12 negCount++;
13 if (firstNeg == -1) firstNeg = i;
14 lastNeg = i;
15 }
16 i++;
17 }
18 int end = i - 1;
19 if (negCount % 2 == 0) {
20 maxLen = Math.max(maxLen, end - start + 1);
21 } else {
22 maxLen = Math.max(maxLen, Math.max(end - firstNeg, lastNeg - start));
23 }
24 }
25 return maxLen;
26 }
27 }
28
29 public static void main(String[] args) {
30 Solution sol = new Solution();
31 int[] nums = {1, -2, -3, 4};
32 System.out.println("Max Length: " + sol.getMaxLen(nums));
33 }
34}

Time & Space Complexity

  • Time complexity: O(n) — Two linear scans across segments take O(n) total time.
  • Space complexity: O(n) — O(n) auxiliary list to store indices of zeros and negatives.

3. Constant Space Two-State DP (Optimal)

Intuition

At each number num: 1. If num > 0: pos = pos + 1; neg = neg > 0 ? neg + 1 : 0. 2. If num < 0: newPos = neg > 0 ? neg + 1 : 0; newNeg = pos + 1; update pos = newPos, neg = newNeg. 3. If num == 0: pos = 0, neg = 0. Maintain maxLen = max(maxLen, pos). This handles all transitions in a single pass without extra memory.

When to apply: Use as the optimal single-pass O(n) time, O(1) space solution.

Two-Register Dynamic Programming (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
A positive element extends the positive subarray length by 1
Visual state
Values and pointers at this exact step
pointers
S
1
-2
-3
4
0
↑ i=0
1
2
3
Variables at this step
i
0
val
1
posLen
1
negLen
0
maxLen
1
Check / comparison
i = 0: nums[0] = 1 > 0. Positive element
Decision / next transition
posLen = posLen + 1 = 1. negLen = (negLen > 0 ? negLen + 1 : 0) = 0. maxLen = 1.
Why this step matters

A positive element extends the positive subarray length by 1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int getMaxLen(int[] nums) {
4 int pos = 0, neg = 0, maxLen = 0;
5 for (int x : nums) {
6 if (x == 0) {
7 pos = 0;
8 neg = 0;
9 } else if (x > 0) {
10 pos++;
11 neg = neg > 0 ? neg + 1 : 0;
12 } else {
13 int temp = pos;
14 pos = neg > 0 ? neg + 1 : 0;
15 neg = temp + 1;
16 }
17 maxLen = Math.max(maxLen, pos);
18 }
19 return maxLen;
20 }
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 int[] nums = {1, -2, -3, 4};
26 System.out.println("Max Length: " + sol.getMaxLen(nums));
27 }
28}

Time & Space Complexity

  • Time complexity: O(n) — A single pass through the array doing O(1) state transitions per element takes O(n) total time.
  • Space complexity: O(1) — Only three integer state variables (pos, neg, maxLen) are maintained in O(1) memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N^2)O(1)Evaluate all subarrays (i, j), multiplying elements and tracking sign.Testing all subarray pairs.
2.Better — Zero-Segment First/Last Negative TrackingO(N)O(N)Split array by 0s. In each segment, if count of negatives is odd, compare removing first vs last negative.Segment storage.
3.Optimal — Constant-Space State DPOptimalO(N)O(1)Single pass updating posLen and negLen state variables.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All negative numbers: e.g. [-1, -2, -3] -> pairs [-1, -2] or [-2, -3] have length 2.
  • Array containing 0s: zeroes properly reset both posLen and negLen to 0.
  • Single negative number: [-5] -> returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Maximum Length of Subarray With Positive Product?

2.Why is the brute force approach suboptimal for large inputs in Maximum Length of Subarray With Positive Product?

3.Which data structure or technique enables the optimal solution for Maximum Length of Subarray With Positive Product?

Back to DSA Sheet