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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Contiguous Array

Number: 525

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, Google, Microsoft, Oracle, Bloomberg, Walmart Labs, Uber, Apple

Problem Description

Given a binary array nums, find the maximum length of a contiguous subarray that has an equal number of 0 and 1.

Key Insights

  • Convert 0s to -1 so that a balanced subarray (equal number of 0s and 1s) sums to zero.
  • Use a prefix sum to track the cumulative sum as you iterate through the array.
  • Use a hash table (or dictionary) to store the first occurrence of each prefix sum.
  • When the same prefix sum is encountered again, it indicates that the subarray between these indices is balanced.

Space and Time Complexity

Time Complexity: O(n) - We iterate through the array once. Space Complexity: O(n) - In the worst case, we store an entry for each prefix sum.

Solution

We use a technique where we convert each 0 in the array to -1. Then, we compute a running prefix sum as we iterate through the array. A prefix sum of 0 at any point indicates that the subarray from the beginning to the current index is balanced. For each prefix sum, if we have seen it before, the subarray between the previous index (where the prefix sum was first seen) and the current index sums to 0. We update the maximum length accordingly. We use a hash table to store the first index where each prefix sum occurs.

Code Solutions

# Python solution for Contiguous Array

def findMaxLength(nums):
    # Dictionary to store the earliest occurrence of each prefix sum
    prefix_indices = {0: -1}
    prefix_sum = 0
    max_length = 0

    # Iterate over the array
    for index, num in enumerate(nums):
        # Convert 0 to -1, keep 1 as is
        if num == 0:
            prefix_sum -= 1
        else:
            prefix_sum += 1
        
        # If the prefix sum has been seen before, a balanced subarray exists
        if prefix_sum in prefix_indices:
            # Calculate the length of the subarray
            current_length = index - prefix_indices[prefix_sum]
            max_length = max(max_length, current_length)
        else:
            # Store the index for this prefix sum if not already seen
            prefix_indices[prefix_sum] = index
    
    # Return the maximum length of balanced subarray
    return max_length

# Example usage:
# print(findMaxLength([0,1,0]))  # Expected output: 2
← Back to All Questions