Watch 10 video solutions for Contiguous Array, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by Techdose has 65,070 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Constraints:
1 <= nums.length <= 105nums[i] is either 0 or 1.Problem Overview: Given a binary array, find the length of the longest contiguous subarray containing the same number of 0s and 1s. The key observation is that equal counts mean their difference becomes zero over a range.
Approach 1: Brute Force (O(n²) time, O(1) space)
The straightforward approach checks every possible subarray. Start from each index i, iterate forward to j, and keep counters for 0s and 1s. Whenever both counts become equal, update the maximum length. This requires two nested loops over the array and constant extra space. The method works for small inputs but becomes slow as the array grows because it evaluates roughly n² subarrays.
This approach is useful when explaining the problem during interviews. It shows that you understand the requirement: a valid subarray must contain equal numbers of the two values. However, it does not scale for large inputs.
Approach 2: Prefix Sum with Hash Map (O(n) time, O(n) space)
The optimal approach converts the problem into a prefix sum problem. Treat every 0 as -1 and every 1 as +1. If two positions have the same cumulative sum, the subarray between them must contain equal numbers of 0s and 1s because their net contribution cancels out.
Traverse the array once while maintaining a running sum. Store the first index where each sum appears in a hash table. When the same sum appears again, compute the subarray length using the stored index and update the maximum. Initialize the map with sum = 0 at index -1 so subarrays starting at index 0 are handled correctly.
This method performs constant-time hash lookups while iterating through the array, giving linear time complexity. It is the standard solution used in competitive programming and technical interviews because it efficiently tracks prefix differences and avoids redundant subarray checks.
Recommended for interviews: Start by explaining the brute force idea to show your reasoning process. Then move to the prefix sum with hash map optimization. Interviewers typically expect the O(n) solution because it demonstrates familiarity with prefix sum patterns and hash-based lookups for tracking previously seen states.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Scan | O(n²) | O(1) | Good for understanding the problem logic or when input size is very small |
| Prefix Sum with Hash Map | O(n) | O(n) | Best general solution; handles large arrays efficiently using prefix difference tracking |