**Key Observation:** if there are same counts of 1's and 0's in sub-array `a[i:j]`

, then the `1-0`

count difference up to index `i-1`

must be same as up to index `j`

(also note that `j-(i-1)`

is the length of sub-array `a[i,j]`

).

Let array `idx[d+n]`

(`n = a.size()`

) be the array to record the first index up to which the `1-0`

count difference is `d`

, then we just need to scan the array `a[]`

to capture the largest index difference `i-idx[d+n]`

for each `i`

.

Note:

- we default
`idx[0+n] = -1`

since we start with no 1's or 0's before scan. - use an array
`vector<int> idx(2*n+1)`

with pre-allocated space is more efficient than a hash map if you know at most how many keys you will have before hand.

```
int findMaxLength(vector<int>& a) {
int res = 0, n = a.size();
vector<int> idx(2*n+1, -1); // idx[d+n] = first index where count of 1's-0's is d
for (int i = 0, d = 0; i < n; res = max(res, i++ -idx[d+n]))
if ((a[i]? ++d : --d) && idx[d+n]<0) idx[d+n] = i;
return res;
}
```