525.Contiguous Array

Tags: [left_sum], [pre_sum], [reuse_input_space], [left_right_pointer], [map]

Com: {fb}

Link: https://leetcode.com/problems/contiguous-array/#/description

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.

Better Understanding Solution:Pre Sum, Map

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        size = len(nums)
        pre_sum = {0: -1}

        left_sum = [0 for _ in xrange(size)]
        left_sum[0] = -1 if nums[0] == 0 else nums[0]
        pre_sum[left_sum[0]] = 0

        for i in xrange(1, size):
            if nums[i] == 0:
                left_sum[i] = -1 + left_sum[i - 1]
            else:
                left_sum[i] = nums[i] + left_sum[i - 1]

            if left_sum[i] not in pre_sum:
                pre_sum[left_sum[i]] = i

        max_len = 0
        for i in xrange(size):
            # Looking for left_sum[i] - X = 0
            # so X = left_sum[i]
            if left_sum[i] in pre_sum:
                sub_len = i - pre_sum[left_sum[i]]
                # the sub_len must be >= 2, because there are only -1, and 1 in array,
                # if the sub_sum == 0, the sub_len must >= 2.
                # But we need check whether pre_sum[left_sum[i]] is equal to i or not.
                if pre_sum[left_sum[i]] != i:
                    max_len = max(max_len, sub_len)

        return max_len

Solution: Pre Sum, Map

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        size = len(nums)

        # Always remember, using this way to record the sum and index,
        # the sum = 0's smallest index is -1.
        pre_sum = {0: -1}

        nums[0] = -1 if nums[0] == 0 else nums[0]
        pre_sum[nums[0]] = 0
        for i in xrange(1, size):
            if nums[i] == 0:
                # convert 0 to -1
                nums[i] = -1

            nums[i] += nums[i - 1]

            # Record the first left_sum <=> i,
            # because we try to make the range bigger.
            if nums[i] not in pre_sum:
                pre_sum[nums[i]] = i

        max_len = 0
        for i in xrange(size):
            # we are trying to find nums[i] - X = 0,
            # so X = nums[i]
            if nums[i] in pre_sum:
                sub_len = i - pre_sum[nums[i]]
                if sub_len >= 2:
                    max_len = max(max_len, sub_len)

        return max_len

Revelation:

• Convert 0 to -1, so that we just need find the subarray,, whose sum == 0. Then we can use map to record the pre sum and its end index.
• Remember the sub_sum = 0's smallest index is -1. Because sum nothing is 0.

Note:

• Time complexity = O(n), n is the number of elements of the given nums.
• Space complexity = O(n), n is the number of elements of the given nums.

Time Limited Exceeded: Left Sum, Reuse Input Space, Left Right Pointer

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        size = len(nums)
        for i in xrange(1, size):
            nums[i] += nums[i - 1]

        max_len = 0
        for left in xrange(size - 1):
            for right in xrange(left + 1, size):
                sub_sum = nums[right]
                if left - 1 >= 0:
                    sub_sum -= nums[left - 1]

                sub_len = right - left + 1
                if sub_sum * 2 == sub_len:
                    max_len = max(max_len, sub_len)

        return max_len

Revelation:

• The number of 0 is equal to the number of 1 means sub_sum * 2 == sub_len.

Note:

• Time complexity = O(n^2), n is the number of element of the give array.
• Space complexity = O(1).