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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/amazon-mock-interview/2022/oa/productof1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.