Solution Explanation: Contiguous Array

The problem asks for the maximum length of a contiguous subarray within a binary array (nums) containing an equal number of 0s and 1s. The optimal solution uses a prefix sum approach combined with a hash table for efficient lookup.

Core Idea:

1. Transforming the Array: We treat 0s as -1. This allows us to represent the balance of 0s and 1s using a simple sum. A subarray with an equal number of 0s and 1s will have a prefix sum of 0.

2. Prefix Sum: We calculate the prefix sum at each index. The prefix sum at index i represents the cumulative sum of elements from index 0 to i (after the 0/-1 transformation).

3. Hash Table (Dictionary): A hash table (or dictionary) is used to store each unique prefix sum encountered and its corresponding index. This allows us to quickly check if a prefix sum has occurred before.

4. Finding the Subarray: If we encounter a prefix sum that already exists in the hash table, it implies that the subarray between the previous occurrence of that prefix sum and the current index has an equal number of 0s and 1s. The length of this subarray is the difference between the current index and the index stored in the hash table.

Algorithm:

1. Initialize a hash table d with {0: -1}. This handles the case where the subarray starts at index 0.
2. Initialize ans (the maximum length) and s (the prefix sum) to 0.
3. Iterate through the input array nums:
   • If nums[i] is 0, subtract 1 from s; otherwise, add 1 to s.
   • Check if s exists as a key in d:
     • If it does, calculate the length of the subarray (i - d[s]) and update ans if this length is greater.
     • If it doesn't, add s and its index i to d.
4. Return ans.

Time Complexity: O(n) - The algorithm iterates through the array once. Hash table lookups and insertions are considered O(1) on average.

Space Complexity: O(n) - In the worst case, the hash table might store all prefix sums, which is proportional to the length of the array.

Code Examples (Python, Java, C++, Go, TypeScript, JavaScript):

The code examples in the provided markdown already demonstrate the algorithm effectively across multiple languages. The core logic remains consistent: prefix sum calculation, hash table use, and maximum length tracking. Each language's syntax is used appropriately.

Example Walkthrough (Python):

Let's consider nums = [0,1,0,1,1,0]:

1. d = {0: -1}
2. Iteration 1: s = -1, d = {0: -1, -1: 0}
3. Iteration 2: s = 0, ans = max(0, 1 - (-1)) = 2, d = {0: -1, -1: 0, 0: 1}
4. Iteration 3: s = -1, ans = max(2, 2 - 0) = 2, d = {0: -1, -1: 0, 0: 1, -1: 2}
5. Iteration 4: s = 0, ans = max(2, 3 - 1) = 2, d = {0: -1, -1: 0, 0: 1, -1: 2, 0: 3}
6. Iteration 5: s = 1, d = {0: -1, -1: 0, 0: 1, -1: 2, 0: 3, 1: 4}
7. Iteration 6: s = 0, ans = max(2, 5 - 3) = 2, d = {0: -1, -1: 0, 0: 1, -1: 2, 0: 3, 1: 4, 0: 5}

The maximum length is 2.