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.

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].

1. 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.

2. First Element (0):

   • The first element is 0, which resets both positiveCount and negativeCount to 0.
   • positiveCount = 0, negativeCount = 0.
   • maxLength remains 0.

3. 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).

4. 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.

5. 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).

6. 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.

7. 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.

8. 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.

9. Final Output:

   • After processing all elements, the maxLength found is 5.

Code

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.