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


  • 1
    C

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

Log in to reply
 

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