525-contiguous-array

Try it on leetcode

Description

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

 

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

 

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

Solution(Python)

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        return self.optimized(nums)

    """
    Idea:
    lets take a subarray of index between [i:j] in nums
    
    how do we find the whether it contains equal number of 0 and 1?
    
    we need Hashtable storing the frequency of 0 and 1 if they are same then it's a possible solution we could use a separate counter for 1 and 0
    
    
    Brutforce solution is to generate all possible contiguos subarray and check if it is valid and whether it is maximum or not is so store them in separate variable
    
    Time Complexity: O(n^2)
    Space Complexity: O(1) 
    """

    def bruteforce(self, nums: List[int]) -> int:
        n = len(nums)
        maxLen = 0

        for i in range(n):
            zeroCount = 0
            oneCount = 0
            for j in range(i, n):

                if nums[j]:
                    oneCount += 1
                else:
                    zeroCount += 1

                if oneCount == zeroCount and zeroCount + oneCount > maxLen:
                    maxLen = zeroCount + oneCount
        return maxLen

    """
    Idea:
   while on a single pass what if we store the count in the hasmap with it's respective index
    both count can be combined by having a single variable that increaments on one and decrements on 0
    
    when a count is encountered on Hashmap update the maxlen since the count resets to 0 on subarray with equal number of 1s and 0s 
    
    Time Complexity: O(n)
    Space Complexityt: O(n)
    """

    def optimized(self, nums: List[int]) -> int:
        Hashmap = {0: -1}
        maxLen = 0
        cnt = 0

        for i in range(len(nums)):
            cnt += 1 if nums[i] else -1
            if cnt in Hashmap:
                Len = i - Hashmap[cnt]
                if Len > maxLen:
                    maxLen = Len
            else:
                Hashmap[cnt] = i

        return maxLen