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


  • 0

    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;
        }
    

Log in to reply
 

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