LeetCode 525. Contiguous Array

Description

https://leetcode.com/problems/contiguous-array/

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.

Example 2:

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

Note: The length of the given binary array will not exceed 50,000.

Explanation

encounter 1, count plus 1; encounter 0, count minus 1. if count exist in map, means numbers of 0 and 1 equal.

Python Solution

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

        return max_count

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