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.
The idea is to transform the array by converting 0s to -1s, which allows us to restate the problem as finding the longest contiguous subarray with a sum of 0. We can use a hash map to store the first occurrence of each prefix sum.
In this C solution, we allocate an array hashMap to store the first indices of various counts. We initialize the map to -2, and the theoretical zero balance to -1. As we iterate over the array, we update the count for either 0s or 1s. We check if this count has been seen before and update the maximum length accordingly.
Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(n) for the hash map storage.
This simple approach checks every possible subarray and calculates its sum, verifying if it has an equal number of 0s and 1s. This method, while simple, serves as an exercise in understanding the problem better prior to using an optimized solution.
This brute-force method iterates over each possible starting point and ending point of a subarray, counting the number of 0s and 1s and checking their equality. This gives a straightforward, albeit inefficient solution.
Time Complexity: O(n^2)
Space Complexity: O(1), as we do not use extra space other than primitive variables.
According to the problem description, we can treat 0s in the array as -1. In this way, when encountering a 0, the prefix sum s will decrease by one, and when encountering a 1, the prefix sum s will increase by one. Therefore, suppose the prefix sum s is equal at indices j and i, where j < i, then the subarray from index j + 1 to i has an equal number of 0s and 1s.
We use a hash table to store all prefix sums and their first occurrence indices. Initially, we map the prefix sum of 0 to -1.
As we iterate through the array, we calculate the prefix sum s. If s is already in the hash table, then we have found a subarray with a sum of 0, and its length is i - d[s], where d[s] is the index where s first appeared in the hash table. If s is not in the hash table, we store s and its index i in the hash table.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Prefix Sum with Hash Map | Time Complexity: O(n), where n is the length of the input array. |
| Brute Force Approach | Time Complexity: O(n^2) |
| Prefix Sum + Hash Table | — |
| 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 |
Contiguous array | Leetcode #525 • Techdose • 65,070 views views
Watch 9 more video solutions →Practice Contiguous Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor