What is the time complexity of Maximum Length of Subarray With Positive Product?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Maximum Length of Subarray With Positive Product?

This problem uses Array, Dynamic Programming, Greedy. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Maximum Length of Subarray With Positive Product?

Insight 1: The sign of the product is determined by the number of negative numbers. An even number of negative numbers results in a positive product, while an odd number results in a negative product. Insight 2: Zeros act as dividers, splitting the array into independent subarrays. The maximum length positive product subarray must lie entirely within a segment bounded by zeros (or the start/end of the array).

Which companies ask LeetCode 1567. Maximum Length of Subarray With Positive Product in interviews?

This problem is frequently asked at Arcesium.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Maximum Length of Subarray With Positive Product - LeetCode 1567 Solution

Maximum Length of Subarray With Positive Product - Complete Solution Guide

Maximum Length of Subarray With Positive Product is LeetCode problem 1567, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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: 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 produ

Detailed Explanation

The problem asks us to find the maximum length of a contiguous subarray within a given integer array `nums` such that the product of all elements in the subarray is positive. A subarray is a consecutive sequence of elements within the array. The key constraint is that the product must be strictly positive, meaning zero values cannot be included in valid subarrays.

Solution Approach

The solution uses dynamic programming to maintain the lengths of the longest positive and negative product subarrays ending at each index. The algorithm iterates through the array, updating these lengths based on the current element. If the current element is positive, the positive length increases by one, and the negative length increases by one if it was already positive. If the current element is negative, the positive and negative lengths swap roles, incrementing if they were non-zero. If the element is zero, both lengths are reset to zero. The maximum positive length encountered so far is tracked and returned.

Step-by-Step Algorithm

Step 1: Initialize `max_len`, `pos_len`, and `neg_len` to 0. `max_len` will store the maximum length of a subarray with a positive product found so far. `pos_len` will store the length of the longest subarray with a positive product ending at the current index. `neg_len` will store the length of the longest subarray with a negative product ending at the current index.
Step 2: Iterate through the input array `nums`.
Step 3: For each element `num` in `nums`:
Step 4: If `num` is positive:
Step 4a: Increment `pos_len` by 1.
Step 4b: If `neg_len` is greater than 0, increment `neg_len` by 1 (because multiplying a negative product by a positive number maintains the negative product).
Step 5: Else if `num` is negative:
Step 5a: Store the value of `neg_len` in a temporary variable `temp` before modifying `pos_len` and `neg_len`.
Step 5b: If `neg_len` is greater than 0, set `pos_len` to `neg_len` + 1. Otherwise, set `pos_len` to 0 (because multiplying a negative product by a negative number results in a positive product).
Step 5c: Set `neg_len` to `temp + 1` if it was greater than 0, 0 otherwise. `temp+1` since we now have 1 more neg number. If temp was 0 we still need to add the negative number to the negative len and it will be 1
Step 5d: `neg_len = pos_len + 1` as a negative number times a positive makes it negative. It will be 1 if pos_len is 0.
Step 6: Else (if `num` is zero):
Step 6a: Reset both `pos_len` and `neg_len` to 0 (because any subarray containing a zero will have a product of zero).
Step 7: Update `max_len` to be the maximum of its current value and `pos_len`.
Step 8: After iterating through all elements in `nums`, return `max_len`.

Key Insights

Insight 1: The sign of the product is determined by the number of negative numbers. An even number of negative numbers results in a positive product, while an odd number results in a negative product.
Insight 2: Zeros act as dividers, splitting the array into independent subarrays. The maximum length positive product subarray must lie entirely within a segment bounded by zeros (or the start/end of the array).
Insight 3: We can keep track of the lengths of the longest positive and negative product subarrays ending at each index. When encountering a negative number, the positive and negative lengths swap roles (with adjustments for zero lengths).

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Dynamic Programming, Greedy.

Companies

Asked at: Arcesium.

Maximum Length of Subarray With Positive Product | LeetCode 1567

Medium

Array Dynamic Programming Greedy

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int getMaxLen(int[] nums) {
        int max_len = 0;
        int pos_len = 0;
        int neg_len = 0;
        
        for (int num : nums) {
            if (num > 0) {
                pos_len += 1;
                if (neg_len > 0) {
                    neg_len += 1;
                }
            } else if (num < 0) {
                int temp = (neg_len > 0) ? neg_len + 1 : 0;
                neg_len = pos_len + 1;
                pos_len = temp;
            } else {
                pos_len = 0;
                neg_len = 0;
            }
            
            max_len = Math.max(max_len, pos_len);
        }
        
        return max_len;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1567: Maximum Length of Subarray With Positive Product - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Greedy

Companies

Arcesium

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1567

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

15 steps

1
Step 1: Initialize `max_len`, `pos_len`, and `neg_len` to 0. `max_len` will store the maximum length of a subarray with a positive product found so far. `pos_len` will store the length of the longest subarray with a positive product ending at the current index. `neg_len` will store the length of the longest subarray with a negative product ending at the current index.
2
Step 2: Iterate through the input array `nums`.
3
Step 3: For each element `num` in `nums`:
4
Step 4: If `num` is positive:
5
Step 4a: Increment `pos_len` by 1.
6
Step 4b: If `neg_len` is greater than 0, increment `neg_len` by 1 (because multiplying a negative product by a positive number maintains the negative product).
7
Step 5: Else if `num` is negative:
8
Step 5a: Store the value of `neg_len` in a temporary variable `temp` before modifying `pos_len` and `neg_len`.
9
Step 5b: If `neg_len` is greater than 0, set `pos_len` to `neg_len` + 1. Otherwise, set `pos_len` to 0 (because multiplying a negative product by a negative number results in a positive product).
10
Step 5c: Set `neg_len` to `temp + 1` if it was greater than 0, 0 otherwise. `temp+1` since we now have 1 more neg number. If temp was 0 we still need to add the negative number to the negative len and it will be 1
11
Step 5d: `neg_len = pos_len + 1` as a negative number times a positive makes it negative. It will be 1 if pos_len is 0.
12
Step 6: Else (if `num` is zero):
13
Step 6a: Reset both `pos_len` and `neg_len` to 0 (because any subarray containing a zero will have a product of zero).
14
Step 7: Update `max_len` to be the maximum of its current value and `pos_len`.
15
Step 8: After iterating through all elements in `nums`, return `max_len`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The solution iterates through the input array once, performing constant-time operations at each step. Therefore, the time complexity is linear, O(n). The solution uses a fixed number of variables (`max_len`, `pos_len`, `neg_len`, and `temp`), regardless of the input size. Therefore, the space complexity is constant, O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Prefix Product Approach

Calculate the prefix product of the array. If the prefix product becomes positive, update the maximum length. If it becomes negative, store the index and wait for it to become positive again. Handle zeros by resetting the prefix product.

Time: O(n)Space: O(n) to store the prefix product (can be optimized to O(1) by not explicitly storing).

Trade-offs: This approach requires more space and can be slightly more complex to implement than the dynamic programming approach. The dynamic programming approach is more efficient in terms of space usage.

✨

Key Insights

1Insight 1: The sign of the product is determined by the number of negative numbers. An even number of negative numbers results in a positive product, while an odd number results in a negative product.
2Insight 2: Zeros act as dividers, splitting the array into independent subarrays. The maximum length positive product subarray must lie entirely within a segment bounded by zeros (or the start/end of the array).
3Insight 3: We can keep track of the lengths of the longest positive and negative product subarrays ending at each index. When encountering a negative number, the positive and negative lengths swap roles (with adjustments for zero lengths).

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Greedy Algorithm

Making the best choice at each step without looking ahead.

Edge Cases

Edge case 1: Empty input array: The code implicitly handles this, as the loop won't execute and `max_len` will remain 0, which is the correct result.
Edge case 2: Array with only zeros: The `pos_len` and `neg_len` will always be reset to 0, and `max_len` will remain 0, which is correct.
Edge case 3: Array with all positive numbers: `pos_len` will increment at each step, and `max_len` will eventually equal the length of the array, which is the correct result.
Edge case 4: Array with all negative numbers: The `pos_len` and `neg_len` will alternate. If the length of the array is even, `max_len` will equal the length of the array. If the length of the array is odd, `max_len` will be 0.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where a zero is encountered properly. Zeros effectively break the array into smaller sub-arrays, and any existing `pos_len` and `neg_len` should be reset.

✗Common mistake 2: Not swapping the `pos_len` and `neg_len` correctly when a negative number is encountered. A temporary variable is crucial to store the previous `neg_len` before calculating the new `pos_len`.

✗Common mistake 3: Failing to reset `pos_len` to 0 when you are calculating new `neg_len` when encountering a negative number.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Financial data analysis. Identifying periods of sustained positive growth (positive product of price changes) in stock prices or other financial instruments.

🏦Real-world scenario 2: Signal processing. Analyzing the sign of a signal over time to identify segments with consistently positive or negative values.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 6, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Maximum Length of Subarray With Positive Product"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?