525. Contiguous Array - Detailed Explanation

Problem Statement

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

Example 1

• Input: [0, 1]
• Output: 2
• Explanation: The entire array has one 0 and one 1, so the maximum subarray length is 2.

Example 2

• Input: [0, 1, 0]
• Output: 2
• Explanation: The subarray [0, 1] (or [1, 0]) has an equal number of 0s and 1s.

Example 3

• Input: [0, 0, 1, 0, 0, 0, 1, 1]
• Output: 6
• Explanation: The subarray [0, 1, 0, 0, 0, 1] has three 0s and three 1s.

Constraints:

• The length of the array can be large (up to 10⁵ elements).
• Each element is either 0 or 1.

Hints

1. Prefix Sum Transformation:
   Consider treating each 0 as -1 and each 1 as +1. The problem then becomes finding a subarray with a cumulative sum of 0.

2. Hash Map to Store Cumulative Sum:
   Use a hash map (or dictionary) to store the earliest index where each cumulative sum occurs. This helps quickly identify the length of a subarray that sums to 0.

Approaches

Brute Force Approach

• Idea:
  Check every possible contiguous subarray and count the number of 0s and 1s.

• Steps:

  1. Iterate over all possible start and end indices.
  2. For each subarray, count the 0s and 1s.
  3. If the counts are equal, update the maximum length.

• Complexity:

  • Time: O(n²) or O(n³) if not optimized, which is inefficient for large arrays.
  • Space: O(1)

Optimal Approach: Prefix Sum with Hash Map

• Idea:
  Convert 0s to -1s, then compute a cumulative sum. When the same cumulative sum is seen again, it means the subarray in between has a total sum of 0 (equal number of 0s and 1s).

• Steps:

  1. Initialize a variable count to 0 and a hash map countIndexMap to store the first occurrence of each cumulative sum. Set countIndexMap[0] = -1 to handle the case when the subarray starts at index 0.
  2. Iterate over the array:
     • If the element is 0, subtract 1 from count (i.e., count -= 1).
     • If the element is 1, add 1 to count (i.e., count += 1).
     • If count has been seen before, the subarray between the previous index and the current index has a sum of 0.
     • Update the maximum length accordingly.
     • If count is not in the hash map, store the current index.

• Complexity:

  • Time: O(n) since we traverse the array once.
  • Space: O(n) for storing cumulative sum indices in the hash map.

Complexity Analysis

• Brute Force Approach:

  • Time: O(n²) or worse
  • Space: O(1)

• Optimal (Prefix Sum + Hash Map):

  • Time: O(n)
  • Space: O(n)

Python Code

Step-by-Step Walkthrough and Visual Examples

Consider the array [0, 1, 0, 0, 1, 1].

1. Initialization:

   • count = 0
   • countIndexMap = {0: -1}
   • maxLength = 0

2. Iteration:

   • Index 0:
     • Element: 0 → Update count to -1 (0 becomes -1)
     • countIndexMap does not contain -1, so add {-1: 0}
   • Index 1:
     • Element: 1 → Update count to 0 (since -1 + 1 = 0)
     • countIndexMap contains 0 at index -1.
     • Subarray length = 1 - (-1) = 2 → Update maxLength to 2
   • Index 2:
     • Element: 0 → Update count to -1
     • countIndexMap contains -1 at index 0.
     • Subarray length = 2 - 0 = 2 → maxLength remains 2
   • Index 3:
     • Element: 0 → Update count to -2
     • countIndexMap does not contain -2, so add {-2: 3}
   • Index 4:
     • Element: 1 → Update count to -1
     • countIndexMap contains -1 at index 0.
     • Subarray length = 4 - 0 = 4 → Update maxLength to 4
   • Index 5:
     • Element: 1 → Update count to 0
     • countIndexMap contains 0 at index -1.
     • Subarray length = 5 - (-1) = 6 → Update maxLength to 6

3. Result:

   • The maximum length of a contiguous subarray with equal number of 0s and 1s is 6.

Common Mistakes

• Not Transforming 0s to -1s:
  Without this transformation, counting 0s and 1s becomes less straightforward.

• Missing the Base Case:
  Forgetting to initialize the hash map with count 0 at index -1 can lead to incorrect subarray length calculations.

• Updating Hash Map Incorrectly:
  Overwriting the first occurrence of a cumulative sum instead of storing it only once can lead to shorter subarray lengths being considered.

Edge Cases

• Empty Array:
  Should return 0 as there are no elements to form a subarray.

• Array with All 0s or All 1s:
  There will be no subarray with an equal number of 0s and 1s, so the result should be 0.

• Array with Immediate Balance:
  For example, [0, 1] or [1, 0] should correctly return 2.

Alternative Variations

• Count Occurrences Instead of Maximum Length:
  Modify the problem to count how many contiguous subarrays have an equal number of 0s and 1s.

• Generalized Balance:
  Extend the idea to arrays containing more than two distinct values where you want to balance the counts of two specific values.

Related Problems

• Subarray Sum Equals K (Leetcode 560):
  Given an array of integers and an integer k, find the total number of continuous subarrays whose sum equals k.

• Longest Substring Without Repeating Characters (Leetcode 3):
  Find the length of the longest substring without repeating characters.