Contiguous Array
Longest Subarray with Equal 0s and 1s in
C++
Achraf Mahdi MAJIDI
majidiachrafmahdi@[Link]
August 8, 2025
1 Introduction and Motivation
The ”Contiguous Array” problem asks for the maximum length of a con-
tiguous subarray containing an equal number of 0s and 1s. It beautifully
illustrates how prefix sums and hashing can be used to solve problems in-
volving balance or zero-sum subarrays, and is a classic interview question.
2 Problem Statement
Given a binary array nums, return the maximum length of a contiguous
subarray with an equal number of 0 and 1.
Examples:
• Input: [0,1]
Output: 2
• Input: [0,1,0]
Output: 2
• Input: [0,1,1,1,1,1,0,0,0]
Output: 6
Constraints:
1
• 1 ≤ [Link] ≤ 105
• nums[i] is 0 or 1
3 Algorithm and Approach
This problem is mapped to the largest subarray with sum zero by treating
0s as −1s:
• Convert 0 to −1 in the array. Now, a subarray with equal number of
0s and 1s has a total sum of 0.
• Use a hash map to store the first index where each prefix sum occurs.
• As we iterate, whenever we see the same prefix sum again, it means the
subarray between the two indices sums to 0 (i.e., has equal numbers of
1s and −1s, hence 0s and 1s).
• Track the maximum distance (length) for every such occurrence.
This is a variant of the “maximum length subarray with sum zero” problem.
4 C++ Implementation
Listing 1: Prefix sum and hash map solution for Contiguous Array
1 class Solution {
2 public :
3 int findMaxLength ( vector < int >& nums ) {
4 int prefixSum = 0;
5 unordered_map < int , int > prefixSumToIndex ;
6 int maxlen = 0;
7 int n = nums . size () ;
8 prefixSumToIndex [0] = -1;
9 for ( int i = 0; i < n ; i ++) {
10 if ( nums [ i ] == 0) {
11 nums [ i ] = -1;
12 }
13 }
14 for ( int i = 0; i < n ; i ++) {
15 prefixSum = prefixSum + nums [ i ];
2
16 if ( prefixSumToIndex . find ( prefixSum ) !=
prefixSumToIndex . end () ) {
17 maxlen = max ( maxlen , i - prefixSumToIndex [
prefixSum ]) ;
18 }
19 else {
20 prefixSumToIndex [ prefixSum ] = i ;
21 }
22 }
23 return maxlen ;
24 }
25 };
5 Complexity Analysis
Time Complexity: O(n)
Each index is visited once, and all hash map operations are O(1) on average.
Space Complexity: O(n)
In the worst case, the hash map stores O(n) entries.
6 Testing Outcomes
This method is robust and passes:
• Arrays with all 0s or all 1s (returns 0).
• Arrays where the whole array is balanced.
• Edge cases and maximal array length (105 ).
• Cases with multiple ties for maximum length subarrays.
7 Reflections
The prefix sum with hashing trick is a powerful paradigm that generalizes
to other problems involving balances or differences and is widely useful in
segment sum enumeration and zero-sum subarray searches.
3
8 Conclusion
This approach reduces a potentially quadratic search to a linear-time, space-
efficient solution, showing the strength of hash maps and prefix sum trans-
formations in array processing.
Prepared by: Achraf Mahdi MAJIDI
Email: majidiachrafmahdi@[Link]