Contiguous Array

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.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

class Solution:
    def findMaxLength(self, nums: list[int]) -> int:
        """Finds the maximum length of a contiguous subarray with an equal number of 0 and 1.

        Args:
            nums: A binary array (list of integers).

        Returns:
            The maximum length of a contiguous subarray with an equal number of 0 and 1.
        """
        max_length = 0
        count = 0
        count_map = {0: -1}  # Initialize with count 0 at index -1

        for i, num in enumerate(nums):
            if num == 0:
                count -= 1
            else:
                count += 1

            if count in count_map:
                max_length = max(max_length, i - count_map[count])
            else:
                count_map[count] = i

        return max_length

Explanation:

1. Initialization:

• max_length: Initialized to 0. This variable will store the maximum length of the subarray found so far.
• count: Initialized to 0. This variable keeps track of the running count of (number of 1s - number of 0s).
• count_map: Initialized to {0: -1}. This dictionary stores the first occurrence of each count value. The initial entry 0: -1 handles the case where a subarray starting from the beginning has an equal number of 0s and 1s.

1. Iteration:

• The code iterates through the nums array, element by element.
• For each element, it updates the count based on whether the element is 0 or 1.
  • If num == 0, count is decremented.
  • If num == 1, count is incremented.

1. Checking for Equal Number of 0s and 1s:

• Inside the loop, the code checks if the current count is already present in the count_map.
  • If it is, it means that there is a subarray between the previous occurrence of this count and the current index i that has an equal number of 0s and 1s. The length of this subarray is i - count_map[count], so the max_length is updated accordingly.
  • If it isn't, it means this is the first time we've encountered this count value, so we add the count and the current index to the count_map.

1. Return Value:

• After iterating through the entire array, the function returns the max_length, which represents the maximum length of a contiguous subarray with an equal number of 0s and 1s.

Example:

Let's trace the execution with the input nums = [0, 1, 0, 1, 1, 0, 0, 0].

i	num	count	count_map	max_length
-	-	0	{0: -1}	0
0	0	-1	{0: -1, -1: 0}	0
1	1	0	{0: -1, -1: 0}	2
2	0	-1	{0: -1, -1: 0}	2
3	1	0	{0: -1, -1: 0}	4
4	1	1	{0: -1, -1: 0, 1:4}	4
5	0	0	{0: -1, -1: 0, 1:4}	6
6	0	-1	{0: -1, -1: 0, 1:4}	6
7	0	-2	{0: -1, -1: 0, 1:4, -2: 7}	6

The function will return 6.

Big O Run-time Analysis:

The solution has a time complexity of O(n), where n is the length of the input array nums. This is because the code iterates through the array only once.

Big O Space Usage Analysis:

The space complexity is O(n) in the worst case. This occurs when all the prefix sums are distinct, and the count_map stores n distinct entries.

Edge Cases:

1. Empty Array: If the input array nums is empty, the function should return 0. The current code handles this case correctly because the loop won't execute, and the initial value of max_length (0) will be returned.

2. Array with Only 0s or Only 1s: If the array contains only 0s or only 1s, there will be no subarray with an equal number of 0s and 1s. In this case, the function will correctly return 0 because the count_map will not contain any duplicate counts other than 0.

3. Large Array: The code should handle large arrays (up to 10^5 elements according to the constraints) without any issues, as the time complexity is linear.