525. Contiguous Array

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Brute Force	For every subarray, count 0s and 1s; if equal, update max length.	\(O(n^2)\)	\(O(1)\)
Hash Map (Optimal)	Use a running count (increment for 1, decrement for 0) and store first occurrence of each count in a hash map. If the same count is seen again, the subarray between indices has equal 0s and 1s.	\(O(n)\)	\(O(n)\)

Implementation

PythonJavaScriptGo

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        result = 0
        num_zeros = 0
        num_ones = 0

        prefix_diff = {}
        for i, n in enumerate(nums):
            num_zeros += 1 if n == 0 else 0
            num_ones += 1 if n == 1 else 0

            diff = num_ones - num_zeros
            if diff == 0:
                result = num_zeros + num_ones
            else:
                if diff not in prefix_diff:
                    prefix_diff[diff] = i
                else:
                    j = prefix_diff[diff]
                    result = max(result, i-j)
        return result