Contiguous Array

Leetcode Problem 525: Contiguous Array

Problem Summary

Given a binary array nums (containing only 0s and 1s), find the maximum length of a contiguous subarray with an equal number of 0s and 1s.

Constraints:

• The array has between 1 and 100,000 elements.
• Each element is either 0 or 1.

Techniques

• Array
• Hash Table
• Prefix Sum

Solution

function findMaxLength(nums: number[]): number {
    let prefixSum = 0;
    let maxSubarray = 0
    let previousPrefixSum = new Map<number, number>()

    previousPrefixSum.set(0, -1)

    for (let i = 0; i < nums.length; i++) {
        prefixSum = prefixSum + (nums[i] === 0 ? -1 : 1)

        if (previousPrefixSum.has(prefixSum)) {
            maxSubarray = Math.max(maxSubarray, i - previousPrefixSum.get(prefixSum)!)
        } 
          
        if (!previousPrefixSum.has(prefixSum)) {
            previousPrefixSum.set(prefixSum, i)
        } 
    }

    return maxSubarray    
};

console.log(findMaxLength([0, 0, 1, 0, 1, 0, 0, 0]))