loading...

Contiguous Array - LeetCode

chakrihacker profile image Subramanya Chakravarthy ・1 min read

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]

Output: 2

Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Contiguous Array

Algorithm:

  1. Initialize two variables curSum and max
  2. Loop through the array and increment curSum by 1 if nums[i] is 1 else decrement 1
  3. Now you can encounter two cases

    1. Sub array formed from index 0

      In this case just take the current index and add 1

      In above examples it would be 1+1 = 2 for 1st example and 3+1 = 4 for 2nd example

    2. Sub Array formed after index 0

      In this scenario you have to find the previous index of cursum and subtract it

      In above image it would be 5-1 = 4

Here's the Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function(nums) {
    let curSum = 0, max =0;
    let map = new Map();

    for(let i = 0; i < nums.length; i++) {
        if(nums[i] == 0) {
            curSum--;
        } else {
            curSum++;
        }

        if(curSum == 0) {
            max = i + 1
        }

        if(map.has(curSum)) {
            max = Math.max(max, i - map.get(curSum))
        } else {
            map.set(curSum, i)
        }
    }

    return max;
};

You can optimize the if condition where curSum == 0 by adding a value into map {0: -1}

Now, in the condition map.has(curSum), it will be something like 1 - (-1) = 2

Discussion

markdown guide