# Maximum Length of Subarray With Positive Product - Leet Code Solution

August 31, 2020

## Problem Statement

Maximum Length of Subarray With Positive Product.

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

``````Input: nums = [1,-2,-3,4]
Output: 4

Input: nums = [0,1,-2,-3,-4]
Output: 3``````

Note: You can include value `0` in your range as this will make product zero.

## Solution

Note: We don’t have to include value-0 in our result. This adds to additional complexity to problem.

Lets think of sliding window kind of solution where we keep track of some indexes and calculate the result.

Few things to keep in mind:

• You can not leave a negative number as it is.
As multiplication of two negative numbers is positive
• You don’t need to actually multiply numbers. The question is about maximum subarray length which multiplies to a positive result.
• You just need to keep a track of how many numbers multiplies to a positive result.
• If your negative counts becomes odd, you would want to remove a negative number from your range.

### Lets talk about some helper variables

Lets talk about some of the variables we will need in this problem.

Negative Count
You need a variable to keep the count the negatives till your iterator index.

Index of Zero
You will need an index of when you last found a `zero`.

Index of first negative number
This will be required in case you encountered negative count to be odd. You would want to calculate length of array excluding first negative number.

### Code

Alright, lets look at the code.

``````public int getMaxLen(int[] nums) {
int max = 0;

int firstNegativeIndex = -1;
int negativeCount = 0;

int zeroIndex = -1;

for (int i=0; i<nums.length; i++) {
//{-1,-2,-3,0,1};
if (nums[i] < 0) {
negativeCount ++;
//update firstNegativeIndex for first time
if (firstNegativeIndex == -1) {
firstNegativeIndex = i;
}
else {
//if its a negative number and count becomes even
if (negativeCount % 2 == 0) {
max = Math.max(max, i-zeroIndex);
}
}
}
else if (nums[i] == 0) {
//reset everything
firstNegativeIndex = -1;
negativeCount = 0;
zeroIndex = i;
}
else {
if (negativeCount % 2 == 0) {
max = Math.max(max, i-zeroIndex);
}
else {
max = Math.max(max, i-firstNegativeIndex);
}
}
}

return max;
}``````

### Complexity

Its `O(n)`

## Similar Posts

### Add two numbers(reverse order) link list Problem - Leet Code Solution

Problem Statement You are given two non-empty linked lists representing two non…

### Replace all spaces in a string with %20

Problem Statement Replace all spaces in a string with ‘%20’ (three characters…

### How to calculate First Common Ancestor of two Nodes in Binary Tree

First try to understand question. Its a binary tree, not a binary search tree…

### How to calculate angle between hour and minute hand, given a time

This problem is a simple mathematical calculation. Lets start deriving some…

### Determine if a string has all unique characters

Problem Implement an algorithm to determine if a string has all the characters…

### Swap Nodes Pairs in Link List - Leet Code Solution

Problem Statement Given a linked list, swap every two adjacent nodes and return…

## Latest Posts

In this post, we will see some of the frequently used concepts/vocabulary in…

System design interview is pretty common these days, specially if you are having…

### Find the maximum sum of any continuous subarray of size K

Introduction You are given an array of integers with size N, and a number K…

### Graph Topological Sorting - Build System Order Example

Graph Topological Sorting This is a well known problem in graph world…

### Binary Tree - Level Order Traversal

Problem Statement Given a Binary tree, print out nodes in level order traversal…

### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…