aboutsummaryrefslogtreecommitdiff
path: root/contiguous_array.py
blob: 8bd17a5e63879e9455f5da4555f0fea5b368ac9f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 525. Contiguous Array

"""
given a binary array 'nums' return the maximum length of a contiguous
subarray with an equal number of 0 and 1.
"""


class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt, max_length = 0, 0
        table = {0: 0}
        for idx, n in enumerate(nums, 1):
            if n == 0:
                cnt -= 1
            else:
                cnt += 1
            if cnt in table:
                max_length = max(max_length, idx - table[cnt])
            else:
                table[cnt] = idx
        return max_length


if __name__ == "__main__":
    obj = Solution()
    print(obj.findMaxLength([0, 1]))
    print(obj.findMaxLength([0, 1, 0]))