https://leetcode.com/problems/contiguous-array

Let us change all 0 in our array with -1. Then we need to find the contiguous subarray with sum equal to zero. There are still O(n^2) different contiguous subarrays, but we do not need to evaluate them all. If we evaluate all cumulative sums, then we need to find two cumulative sums which are equal and have the biggest distance. Example:

nums = [1, 0, 0, 1, 1, 1, 1, 0, 1] ->[1, -1, -1, 1, 1, 1, 1, -1, 1] -> [1, 0, -1, 0, 1, 2, 3, 2, 3] and the biggest distance between equal elements is 4, element number 0 and element number 4.

We are going to keep ind hashtable, where for each value of cumulative sum we keep indexes for the first and for the last element with this value in our cumulative sum. Continue with our example:

ind[0] = [1,3]
ind[1] = [0,4]
ind[-1] = [2,2]
ind[2] = [5,7]
ind[3] = [6,8]

Complexity We need to go through our nums twice: first, when we build cumulative sums and then when we create our ind hash-table, hence we have O(n) time complexity. Also, there can be at most 2n + 1 elements in our hash-table - with values from -n to n (in fact not more than n of them will be there, because we have only n cumulative sums). So time complexity is also O(n).

class Solution:
    def findMaxLength(self, nums):
        nums = list(accumulate([x * 2 - 1 for x in nums]))
        ind = defaultdict(list)
        ind[0] = [-1,-1]
        for i in range(len(nums)):
            if not ind[nums[i]]:
                ind[nums[i]] = [i,i]
            else:
                ind[nums[i]][1] = i
      
        max_len = 0
        for i in ind:
            max_len = max(max_len,ind[i][1]-ind[i][0])
        return max_len

If you like the solution, you can upvote it on leetcode discussion section: Problem 0525