Contiguous Array - LeetCode Daily Challenge

Problem Statement

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.

Try here before watching the video.

Video Explanation

Java Code

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> sumIndexMap = new HashMap<>();
        sumIndexMap.put(0, -1);

        int sum = 0, maxLength = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i] == 1 ? 1 : -1;
            if(sumIndexMap.containsKey(sum)) {
                maxLength = Math.max(maxLength, i - sumIndexMap.get(sum));
            } else {
                sumIndexMap.put(sum, i);
            }
        }

        return maxLength;
    }
}

C++ Code

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> sumIndexMap;
        sumIndexMap[0] = -1;

        int sum = 0, maxLength = 0;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i] == 1 ? 1 : -1;
            if(sumIndexMap.find(sum) != sumIndexMap.end()) {
                maxLength = max(maxLength, i - sumIndexMap[sum]);
            } else {
                sumIndexMap[sum] = i;
            }
        }

        return maxLength;
    }
};

Python Code

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        sum_index_map = {}
        sum_index_map[0] = -1
        
        sum_val = 0
        max_length = 0
        
        for i in range(len(nums)):
            sum_val += 1 if nums[i] == 1 else -1
            if sum_val in sum_index_map:
                max_length = max(max_length, i - sum_index_map[sum_val])
            else:
                sum_index_map[sum_val] = i
        
        return max_length

Javascript Code

var findMaxLength = function(nums) {
    let sumIndexMap = new Map();
    sumIndexMap.set(0, -1);
    
    let sum = 0, maxLength = 0;
    for(let i = 0; i < nums.length; i++) {
        sum += nums[i] === 1 ? 1 : -1;
        if(sumIndexMap.has(sum)) {
            maxLength = Math.max(maxLength, i - sumIndexMap.get(sum));
        } else {
            sumIndexMap.set(sum, i);
        }
    }
    
    return maxLength;
};

Go Code

func findMaxLength(nums []int) int {
    sumIndexMap := make(map[int]int)
    sumIndexMap[0] = -1

    sum := 0
    maxLength := 0
    for i, num := range nums {
        if num == 1 {
            sum++
        } else {
            sum--
        }

        if index, ok := sumIndexMap[sum]; ok {
            maxLength = max(maxLength, i-index)
        } else {
            sumIndexMap[sum] = i
        }
    }

    return maxLength
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Complexity Analysis

Time Complexity: O(N), this is because we're iterating over the whole array once.
Space Complexity: O(N), this is because we're storing sum and in the worst-case scenario the whole array might have only 1s which would effectively create N different sums.