We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Contiguous Array

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem can be transformed by treating 0 as -1, which allows us to calculate the sum of the subarray. A subarray with an equal number of 0s and 1s will have a sum of 0.
  • We can use a hash map to store the first occurrence of each cumulative sum, allowing us to quickly find the length of subarrays that sum to zero.
  • The maximum length can be updated whenever we encounter the same cumulative sum again.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array. Space Complexity: O(n), for storing the cumulative sums in a hash map.

Solution

To solve this problem, we will use a hash map to keep track of the indices of cumulative sums. As we iterate through the array, we will compute the cumulative sum, and if this sum has been seen before, it indicates that the subarray between the previous index and the current index has an equal number of 0s and 1s. We will update our maximum length accordingly.

Code Solutions

def findMaxLength(nums):
    count_map = {0: -1}  # Initialize the map with cumulative sum 0 at index -1
    max_length = 0
    count = 0  # This will keep track of the cumulative sum

    for i in range(len(nums)):
        # Treat 0 as -1
        count += 1 if nums[i] == 1 else -1

        # If the cumulative sum has been seen before
        if count in count_map:
            max_length = max(max_length, i - count_map[count])
        else:
            count_map[count] = i  # Store the first occurrence of the cumulative sum

    return max_length
← Back to All Questions