Contiguous Array
Problem Description
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
Example 1:
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Example 3:
Explanation: [1,1,1,0,0,0] is the longest contiguous subarray with equal number of 0 and 1.
Constraints:
- 1 <= nums.length <= 105
nums[i]is either0or1.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
In the brute force approach, we check all possible subarrays to determine if they contain an equal number of 0s and 1s. This can be done by calculating the sum of elements within every possible subarray where each '0' is treated as -1 and '1' as 1. A subarray with a sum of zero has equal numbers of 0s and 1s.
Code:
- Time Complexity: O(n^2) where (n) is the number of elements in the array. This is due to checking each possible subarray.
- Space Complexity: O(1) since we are not using any extra space related to input size.
2. Prefix Sum + HashMap
Intuition:
To improve efficiency, we can use a prefix sum approach combined with a hash map. The key observation is that if two indices have the same prefix sum, the subarray between them has an equal number of 0s and 1s. We maintain a running sum where we treat 0 as -1 and 1 as 1. The hash map stores the first occurrence of each running sum. If at some index the running sum is the same as at a previous index, the subarray between those indices is balanced.
Code:
- Time Complexity: O(n) where (n) is the number of elements in the array. This is due to traversing the array once.
- Space Complexity: O(n) where (n) is the number of elements in the array. This is due to the space required for the hash map.