Is Maximum Length of Subarray With Positive Product easy or hard?

The problem is typically classified as Medium difficulty. The main challenge is handling sign changes caused by negative numbers and correctly resetting when encountering zero, while still maintaining an O(n) solution.

Maximum Length of Subarray With Positive Product Python/Java solution

Implementations in Python, Java, C++, C#, and JavaScript follow the same logic: iterate through the array, update positive and negative lengths based on the current value, reset on zeros, and track the maximum positive length found.

How to solve Maximum Length of Subarray With Positive Product in O(n)?

Traverse the array while tracking the length of subarrays ending at the current index with positive and negative products. Positive numbers extend the positive length, while negative numbers swap the positive and negative lengths. Reset both counters when encountering zero. Keep updating the maximum positive length during the scan.

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

The greedy sign-tracking approach is the most efficient and commonly used method. It maintains two running lengths: one for subarrays with a positive product and one for negative products. Each number updates these states depending on its sign, producing the answer in O(n) time and O(1) space.

Is Maximum Length of Subarray With Positive Product asked at Google/Amazon/Meta?

Variants of sign-based subarray problems and product parity questions appear in interviews at companies like Amazon, Google, and Meta. The problem tests reasoning about negative numbers, greedy state updates, and efficient array traversal.

What data structure is used in Maximum Length of Subarray With Positive Product?

The solution mainly relies on array traversal with constant variables to track state. No complex data structure is required; the algorithm uses counters that store the current lengths of positive and negative product subarrays.

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

The optimal algorithms run in O(n) time because the array is scanned once or twice. Both the greedy sign-tracking method and the two-pass approach use constant extra memory, giving O(1) space complexity.

Description Hints 3 Solution Video 12:45

1567. Maximum Length of Subarray With Positive Product

Medium44.9% acceptance2 companies

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Asked at 2 companies

Arcesium Amazon

Topics

Hints open one at a time

Hint 1

Split the whole array into subarrays by zeroes since a subarray with positive product cannot contain any zero.

Hint 2

If the subarray has even number of negative numbers, the whole subarray has positive product.

Hint 3

Otherwise, we have two choices, either - remove the prefix till the first negative element in this subarray, or remove the suffix starting from the last negative element in this subarray.

12:45

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def getMaxLen(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,-2,-3,4]

Input

[0,1,-2,-3,-4]

Input

[-1,-2,-3,0,1]

Your code is saved on this device.Solution