Contiguous Array - Leetcode Solution

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

Example 1: Input: nums = [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2: Input: nums = [0,1,0] Output: 2 Explanation: [0, 1], [1, 0] is the longest contiguous subarray with equal number of 0 and 1.

Approach: We can use a hash map to store the index of each prefix sum encountered while traversing the array. We start traversing from the beginning of the array and calculate the prefix sum at each index. If the prefix sum is in the hash map, it means that we have encountered the same number of 0's and 1's before, which means there is a contiguous subarray between the previous index and current index with equal number of 0's and 1's. We update the maximum length of such subarray if it is greater than the previous maximum length.

Algorithm:

1. Initialize a hash map "prefix_sum_indices" with 0 as key and value as -1
2. Initialize variable "prefix_sum" as 0 and "max_len" as 0
3. Traverse the given binary array "nums" from 0 to n-1
4. If nums[i] is 0, subtract 1 from "prefix_sum", else add 1 to "prefix_sum"
5. If prefix_sum is already in the hash map, calculate the length of contiguous subarray with equal number of 0's and 1's between current index "i" and previous index "prefix_sum_indices[prefix_sum]". Update "max_len" if this length is greater than "max_len"
6. Else, add "prefix_sum" as key and "i" as value to the hash map
7. Return the "max_len"

Code in Python:

class Solution: def findMaxLength(self, nums: List[int]) -> int: n = len(nums) prefix_sum_indices = {0: -1} prefix_sum = max_len = 0 for i in range(n): if nums[i] == 0: prefix_sum -= 1 else: prefix_sum += 1 if prefix_sum in prefix_sum_indices: max_len = max(max_len, i-prefix_sum_indices[prefix_sum]) else: prefix_sum_indices[prefix_sum] = i return max_len

Time Complexity: O(n), where n is the length of the binary array Space Complexity: O(n), where n is the length of the binary array

1