> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/amazon-mock-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/amazon-mock-interview/2022/oa/productof1.md).

# ProductOf1

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/>