Contiguous Array

This is a nice problem from LeetCode (Problem #525).

Problem: 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.

Example 3:

Input: nums = [0,1,1,1,1,1,0,0,0]

Output: 6

Explanation: [1,1,1,0,0,0] is the longest contiguous subarray with equal number of 0 and 1.

Solution 1 Naive Brute Force Approach

The naive and brute force approach examines every subarray of nums, using two for loops. The outer for loop tracks the start of the subarray and the inner for loop tracks the end of the subarray. When the count of zeroes and ones in the subarray are equal, we update maxLen if the current length is larger than the current maxLen. Upon exiting the loops, maxLen is guaranteed to be equal to the largest contiguous array with equal number of zeroes and ones.

    def findMaxLength(nums):
        maxLen = 0
        for start in range(len(nums)):
            zeroes = ones = 0
            for end in range(start, len(nums)):
                if nums[end] == 0:
                    zeroes += 1
                else:
                    ones += 1
                if zeroes == ones:
                    maxLen = max(maxLen, end - start + 1)
        return maxLen

Runtime The time complexity is obviously $O(n^2)$ due to the doubly nested for loops. The space complexity is $O(1)$ as we are only using constant variables (zeroes, ones, maxLen).

Solution 2 Hash Map Approach

The hash map approach is quite simple. We initialize count to 0. As we iterate through the elements in nums, whenever we encounter a 0, we decrement the count by 1, and whenever we encounter a 1, we increment the count by 1. We store any new values of count in a hash map, where the keys are the counts and the values are the corresponding indexes. When we compute a count, we check if it is already present in the hash map. If this count is already present in the hash map, then we compute the length of the subarray, starting from the index of the previous count and the current index. We update maxLen, if this length is larger than the current maxLen. If the count value is not already present in the hash map, we add it to the hash map.

    def findMaxLength(nums):
        from collections import defaultdict
        count = maxLen = 0
        hashMap = defaultdict(int)
        hashMap[0] = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                count -= 1
            else:
                count += 1
            if count in hashMap:
                maxLen = max(maxLen, i+1 - hashMap[count])
            else:
                hashMap[count] = i+1
        return maxLen

Runtime: The cost of building the hash map is $O(n)$ and the cost of finding the pair that sums to target is also $O(n)$. Hence the runtime is $O(n)$. The space complexity is $O(n)$ due to the need for the hash map.

Back to Hash Map Problems

---

anusha-murali.github.io