ProductOf1

https://leetcode.com/discuss/interview-question/1655441/Amazon-or-OA

A question about Amazon student badges but ultimately the problem was given an arr of -1 or 1, return the maximum subarray length with a product of 1. The array is of size 2 and above and only contains -1 and 1

e.g arr = [-1,-1,1,1,-1], return 4, since index 0 to 3 have the max length with product equal to 1

Similar as LC 1567

Solution 1:

1. Use a sliding window index , called end

2. initialize count of "-1" as 0

3. while end is less than the arr size, increment end

4. if arr[end] == "-1", Save the index of this first occurence of "-1" only once

And always increment the count of -1

1. if count is even , ans = max(ans,end +1) If count is odd and count != 1 ans = max( ans, end - (index_of_1st_occurence_of_-1 + 1) + 1)

Because if the count of -1 is currently odd, the region between the first ever -1 and index end will be even.

Solution 2:

Intuition is traverse input array of size n once and ONLY maintain integer count of -1s and append their index locations in queue

1. if integer count is even, return len(input array) # we found equilibrium

2. if integer count is odd, we want to find a subarray such that we must remove the leftmost or rightmost -1 that is breaking equilibrium ... **so max length of either of these two subarrays **

• arr[ 0 : index of latest queue item (rightmost minus 1) -1 ]

• arr[ index of first queue item (leftmost minus 1) +1 : n]

note: equilibrium just means that there are 0 or even number of -1s .. we dont really care about number of +1s

from collections import deque

def solve(arr):
    l = 0
    r = len(arr)
    q = deque()
    cnt_minus1 = 0
    
    for i in range(r):
    	if arr[i] == -1:
    		cnt_minus1 = cnt_minus1 + 1
    		q.append(i) 
    
    if cnt_minus1 % 2 == 0:
    	return len(arr)
    else: 
    	newLeft = q[0] + 1
    	newRight = q[-1] - 1
    	print(newLeft, newRight)
    	return max((r-newLeft), (newRight-l))
    	
print(solve([-1,-1,-1,-1,-1, 1])) # 5
print(solve([-1,-1,1,1,-1])) # 4 

Very similar: https://www.gyanblog.com/coding-interview/leetcode-solution-max-length-positive-product/