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
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.