Contiguous Array

Problem Statement

Constraints

Solution 1: Prefix Sum and Hash Map

function findMaxLengthPrefixSum(nums) {
    let maxLen = 0;
    let sum = 0;
    const map = new Map();
    map.set(0, -1); // Initialize with sum 0 at index -1

    for (let i = 0; i < nums.length; i++) {
        sum += nums[i] === 0 ? -1 : 1;
        if (map.has(sum)) {
            maxLen = Math.max(maxLen, i - map.get(sum));
        } else {
            map.set(sum, i);
        }
    }
    return maxLen;
} 

const nums1 =  [0,1];
findMaxLengthPrefixSum(nums1);  //output: 2 

const nums2 = [0,1,0];
findMaxLengthPrefixSum(nums2);  //output: 2 

Solution 2: Brute Force Solution

function findMaxLengthBruteForce(nums) {
    let maxLen = 0;
    for (let start = 0; start < nums.length; start++) {
        let count0 = 0, count1 = 0;
        for (let end = start; end < nums.length; end++) {
            if (nums[end] === 0) count0++;
            else count1++;
            if (count0 === count1) {
                maxLen = Math.max(maxLen, end - start + 1);
            }
        }
    }
    return maxLen;
} 

const nums1 =  [0,1];
findMaxLengthBruteForce(nums1);  //output: 2 

const nums2 = [0,1,0];
findMaxLengthBruteForce(nums2);  //output: 2 

Solution 3: Sliding Window

function findMaxLengthSlidingWindow(nums) {
    let maxLen = 0;
    let map = new Map();
    map.set(0, -1);
    let sum = 0;

    for (let i = 0; i < nums.length; i++) {
        sum += nums[i] === 0 ? -1 : 1;
        if (map.has(sum)) {
            maxLen = Math.max(maxLen, i - map.get(sum));
        } else {
            map.set(sum, i);
        }
    }
    return maxLen;
} 

const nums1 =  [0,1];
findMaxLengthSlidingWindow(nums1);  //output: 2 

const nums2 = [0,1,0];
findMaxLengthSlidingWindow(nums2);  //output: 2 

Solution 4: Using Array with Cumulative Sum

function findMaxLengthCumulativeSum(nums) {
    let maxLen = 0;
    const cumulativeSum = [];
    let sum = 0;

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

    const map = new Map();
    map.set(0, -1);

    for (let i = 0; i < cumulativeSum.length; i++) {
        if (map.has(cumulativeSum[i])) {
            maxLen = Math.max(maxLen, i - map.get(cumulativeSum[i]));
        } else {
            map.set(cumulativeSum[i], i);
        }
    }
    return maxLen;
} 

const nums1 =  [0,1];
findMaxLengthCumulativeSum(nums1);  //output: 2 

const nums2 = [0,1,0];
findMaxLengthCumulativeSum(nums2);  //output: 2 

Resources

Frequently asked questions

1. Why are some solutions using a prefix sum approach?

   The prefix sum approach helps to efficiently track the cumulative balance of 0s and 1s. By converting 0s to -1s, the problem transforms into finding subarrays with a cumulative sum of zero. This transformation allows the use of hash maps to quickly find the maximum length of such subarrays.

2. Can the brute force solution be used for large input sizes?

   While the brute force solution is straightforward, it is not efficient for large input sizes due to its O(n^2) time complexity. For arrays with up to 100,000 elements, this solution would be too slow. It's better to use more optimized approaches like prefix sum and hash map.

3. What are the benefits of using a hash map in these solutions?

   A hash map allows for O(1) average time complexity for both insertions and lookups, making it highly efficient for tracking previously seen cumulative sums. This efficiency is crucial for solving the problem in linear time.

4. What are some potential edge cases to consider?

   • Arrays with only one element will not have a valid subarray.

   • Arrays where all elements are the same, like [0,0,0] or [1,1,1], will also not have a valid subarray.

   • Arrays with multiple valid subarrays of different lengths should be tested to ensure the solution finds the longest one.

More Problems Solutions