# Clean C++ O(n) solution using prefix sum and hash table, beating 91%

• Since the array only contains 1 and 0, we can compute the prefix sum by treating the 0 as -1:

Let prefixSum[i] be the sum of array between [0, i] inclusive.

If prefixSum[i] == 0, meaning that the prefix array between [0, i] has equal number of 0's and 1's, and its length is (i).

If prefixSum[i] != 0, let's assume we have another prefixSum[j] which satisfy: prefixSum[i] == prefixSum[j] && j < i.

So between (j, i] range there's a sub-array which has equal number of 1's and 0's, which has a length of (i - j).

We can use a hashtable to keep track of prefixSum[j] when we scan the input array from left to right. (key, value) = (prefixSum[j], j). And we only keep the leftmost j (meaning smallest j for the same prefixSum[j]) so that the length can be maximized.

``````class Solution {
public:
int findMaxLength(vector<int>& nums) {
int prefixSum = 0;
unordered_map<int, int> prefixMap;
int maxLen = 0;

for (int i=0; i<nums.size(); i++) {
prefixSum += nums[i] == 1 ? 1 : -1;
if (prefixSum == 0) {
maxLen = max(maxLen, i+1);
} else {
auto it = prefixMap.find(prefixSum);
if (it == prefixMap.end()) {
prefixMap[prefixSum] = i;
} else {
maxLen = max(maxLen, i - it->second);
}
}
}

return maxLen;
}
};
``````

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