Maximum Length Of Subarray With Positive Product - Leetcode Solution

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

Example 3: Input: nums = [-1,-2,-3,0,1] Output: 2 Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Solution:

Approach: The main idea is to keep track of the negative numbers from the left and right side of the array by using two pointers. The pointers start from the beginning and end of the array. If there are even number of negative numbers from the left side and right side, then the product will be positive otherwise it will be negative. If the product is positive, then we update the maximum length of the subarray with positive product. We keep updating the maximum length of the subarray with positive product until we reach the end of the array.

Algorithm:

1. Initialize two pointers left and right to zero and length to n.
2. Initialize two variables i and j to zero.
3. Iterate while i is less than n: a) If the current element is negative, increment j by one. b) If j is greater than right, update the right pointer to j. c) If the current element is zero, set both i and j equal to the current index plus one. d) If i is greater than right, then reset both left and right pointers to i. e) If the current element is positive and i is greater than left, update the left pointer to i. f) Increment i by one.
4. If there are even number of negative numbers or no negative numbers, then return length minus left plus right minus one, otherwise return the maximum of length minus right and left.

Time Complexity: The time complexity of this algorithm is O(n) as we are iterating through the array only once.

Space Complexity: The space complexity of this algorithm is O(1) as we are not using any extra space other than few variables.

Code:

class Solution { public: int getMaxLen(vector<int>& nums) { int n = nums.size(), left = 0, right = n - 1, i = 0, j = 0, length = 0; while(i < n) { if(nums[i] < 0) j++; if(j > right) right = j; if(nums[i] == 0) { j = i + 1; left = j; } else if(i > right && nums[i] > 0) { left = i; } i++; } if(j % 2 == 0 || j == n) { length = n - left + right - 1; } else { length = max(n - right - 1, left); } return length; } };

1