# Leetcode: Contiguous Array

Contiguous Array

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/contiguous-array
## Basic Ideas: Get sum of subarray. (For each 1, add 1; For each 0, extract 1)
##              And build a hashmap for the fastest position of a given sum.
##
##       For each item nums[i]:
##             If it's 1, find the fastest position k with sum[k] = sum[i] - 1
##             If it's 0, find the faster postion k with sum[k] = sum[i] + 1
##
## Complexity: Time O(n), Space O(n)
class Solution:
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
sums = [None] * length
m = {}
sum_v = 0
for i in range(0, length):
if nums[i] == 1:
sum_v += 1
else:
sum_v -= 1
# get the value of sum
sums[i] = sum_v
# track the longest position
if sum_v not in m:
m[sum_v] = i
else:
m[sum_v] = max(m[sum_v], i)
res = 0
for i in range(0, length):
sum_v = sums[i]
if nums[i] == 1:
if sum_v - 1 in m:
res = max(res, (m[sum_v-1]-i+1))
else:
if sum_v + 1 in m:
res = max(res, m[sum_v+1]-i+1)
return res
```

Share It, If You Like It.