# 5-liner O(N) one-pass beat 100% (with explanation)

• 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:

1. we default `idx[0+n] = -1` since we start with no 1's or 0's before scan.
2. 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.