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).
One Thought to “LeetCode 525. Contiguous Array”