525. Contiguous Array.md

525. Contiguous Array

• Difficulty: Medium.
• Related Topics: Array, Hash Table, Prefix Sum.
• Similar Questions: Maximum Size Subarray Sum Equals k.

Problem

Given a binary array nums, return **the maximum length of a contiguous subarray with an equal number of 0 and **1.

  Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

  Constraints:

• 1 <= nums.length <= 105

• nums[i] is either 0 or 1.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function(nums) {
    var map = {};
    var count = 0;
    var max = 0;
    map[0] = -1;
    for (var i = 0; i < nums.length; i++) {
        count += (nums[i] === 1 ? 1 : -1);
        if (map[count] !== undefined) {
            max = Math.max(max, i - map[count])
        } else {
            map[count] = i;
        }
    }
    return max;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).