Scale Engineer

Maximum Length of Subarray With Positive Product

Med
#1442Time: O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of operations as we check every possible subarray.Space: O(1), as we only use a constant amount of extra space for variables like `maxLength` and `productSign`.1 company
Patterns
Dynamic ProgrammingGreedy
Data structures
Array
Companies
Arcesium

Prompt

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] <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

The brute-force approach is the most straightforward way to solve the problem. It involves generating every possible contiguous subarray, checking if the product of its elements is positive, and keeping track of the maximum length found. To avoid potential integer overflows from calculating the actual product, we only need to track the sign of the product. A zero in a subarray makes its product zero (not positive), and an even number of negative elements results in a positive product.

Algorithm

  • Initialize maxLength to 0.
  • Use a nested loop structure. The outer loop with index i defines the start of a subarray, and the inner loop with index j defines the end.
  • For each subarray nums[i...j], calculate the sign of its product.
  • To do this efficiently, for a fixed i, as j increases, we can maintain the sign of the product of nums[i...j] in O(1) time.
  • Initialize a variable productSign = 1 before the inner loop.
  • Inside the inner loop (for j):
    • If nums[j] is 0, the product becomes 0. No subarray starting at i and including j can have a positive product. So, we break the inner loop.
    • If nums[j] is negative, we flip the sign: productSign *= -1.
    • If productSign is positive (i.e., 1), it means the subarray nums[i...j] has a positive product. We update maxLength = max(maxLength, j - i + 1).
  • After iterating through all possible subarrays, return maxLength.

Walkthrough

We can implement this using two nested loops. The outer loop iterates through all possible starting points i of a subarray, and the inner loop iterates through all possible ending points j. For each subarray nums[i...j], we determine the sign of its product. Instead of re-computing the product for each subarray, we can maintain a running sign. When we extend the subarray from nums[i...j-1] to nums[i...j], we update the sign based on nums[j]. If nums[j] is positive, the sign remains unchanged. If nums[j] is negative, the sign flips. If nums[j] is zero, the product becomes zero, and any longer subarray starting at i will also have a zero product, so we can stop extending from this i. If the sign of the current subarray's product is positive, we update our maximum length.

class Solution {    public int getMaxLen(int[] nums) {        int n = nums.length;        int maxLength = 0;        for (int i = 0; i < n; i++) {            int productSign = 1;            for (int j = i; j < n; j++) {                if (nums[j] == 0) {                    // Product becomes 0, which is not positive.                    // Any subarray extending further will also have a product of 0.                    break;                 } else if (nums[j] < 0) {                    productSign *= -1;                }                                // If product is positive, update maxLength                if (productSign > 0) {                    maxLength = Math.max(maxLength, j - i + 1);                }            }        }        return maxLength;    }}

Complexity

Time

O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of operations as we check every possible subarray.

Space

O(1), as we only use a constant amount of extra space for variables like `maxLength` and `productSign`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for smaller inputs.

Cons

  • The O(n^2) time complexity is too slow for the given constraints (n <= 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  int getMaxLen(int[] nums) {    int f1 = nums[0] > 0 ? 1 : 0;    int f2 = nums[0] < 0 ? 1 : 0;    int res = f1;    for (int i = 1; i < nums.length; ++i) {      if (nums[i] > 0) {        ++f1;        f2 = f2 > 0 ? f2 + 1 : 0;      } else if (nums[i] < 0) {        int pf1 = f1, pf2 = f2;        f2 = pf1 + 1;        f1 = pf2 > 0 ? pf2 + 1 : 0;      } else {        f1 = 0;        f2 = 0;      }      res = Math.max(res, f1);    }    return res;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem