Amazon | Online Assessment| Product of 1
Anonymous User
8893

Problem Statement:
Find a subarray of maximum length such that the product of all the elements in the subarray is 1.

Sample input:
array size: n = 6
array = [1, -1, -1, -1, 1, 1]

Sample output:
4

Explanation:
These are a few of the subarrays whose product is equal to 1:
Subarray with indices from (0,2), length of the subarray is 3
Subarray with indices from (1,2), length of the subarray is 2
Subarray with indices from (2,5), length of the subarray is 4
Subarray with indices from (4,5), length of the subarray is 2

My solution is an O(n^2) but I'm trying figure out how to make it an O(n) solution if possible.

public static int maxSubArrayLength(int[] arr){
        if(arr.length == 0) return 0;
        int maxLen = Integer.MIN_VALUE;
        int curLen = 0;

        for(int i = 0; i < arr.length; i++){
            int product = 1;
            for(int j = i; j < arr.length; j++){
                product = product * arr[j];
                if(product == 1){
                    curLen = j - i + 1;
                    maxLen = Math.max(maxLen, curLen);
                }else{
                    curLen = 0;
                }
            }
        }
        return maxLen;
    }
	```
Comments (11)