Contiguous Array — LeetCode 525 Python Solution

The problem

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

Example

Input

nums = [0,1]

Output

2

Explanation

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

Python solution

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        d = {0: -1}
        ans = s = 0
        for i, x in enumerate(nums):
            s += 1 if x else -1
            if s in d:
                ans = max(ans, i - d[s])
            else:
                d[s] = i
        return ans

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 525. Contiguous Array is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems