.png)
Longest Subarray with Equal 0s and 1s
Problem Statement
You are given a binary array arr consisting only of 0s and 1s.
Your task is to find the length of the longest contiguous subarray that contains an equal number of 0s and 1s.
Example 1
Input
arr = [0, 1]
Output
2
Example 2
Input
arr = [0, 1, 0]
Output
2
Why This Problem Is Important
- Very common interview problem
- Tests prefix sum + hashing concept
- Introduces transformation trick (0 → -1)
- Foundation for subarray sum problems
- Asked in FAANG & product-based companies
Key Insight
Convert:
- 0 → -1
- 1 → +1
Then the problem becomes:
Find the longest subarray with sum = 0
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Prefix Sum + Hash Map (Optimal) | O(n) | O(n) |
Approach 1: Brute Force
Idea
Check every possible subarray and count number of 0s and 1s.
If both counts are equal, update maximum length.
Algorithm
- Initialize maxLen = 0
- For every starting index i
- Initialize zeroCount = 0, oneCount = 0
- For every ending index j
- Update counts
- If zeroCount == oneCount
- Update maxLen = max(maxLen, j - i + 1)
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Approach 1: Brute Force (O(n²))
Input
arr = [0,1,0,1,1,1,0]
Output
4
(Longest subarray with equal 0s and 1s is length 4 → [0,1,0,1])
C
#include
int main() {
int arr[] = {0,1,0,1,1,1,0};
int n = 7, maxLen = 0;
for(int i = 0; i < n; i++) {
int zero = 0, one = 0;
for(int j = i; j < n; j++) {
if(arr[j] == 0) zero++;
else one++;
if(zero == one) {
int len = j - i + 1;
if(len > maxLen)
maxLen = len;
}
}
}
printf("Input: [0,1,0,1,1,1,0]\n");
printf("Output: %d\n", maxLen);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {0,1,0,1,1,1,0};
int n = 7, maxLen = 0;
for(int i = 0; i < n; i++) {
int zero = 0, one = 0;
for(int j = i; j < n; j++) {
if(arr[j] == 0) zero++;
else one++;
if(zero == one)
maxLen = max(maxLen, j - i + 1);
}
}
cout << "Input: [0,1,0,1,1,1,0]" << endl;
cout << "Output: " << maxLen << endl;
return 0;
}
Java
public class LongestSubarray01Brute {
public static void main(String[] args) {
int[] arr = {0,1,0,1,1,1,0};
int maxLen = 0;
for(int i = 0; i < arr.length; i++) {
int zero = 0, one = 0;
for(int j = i; j < arr.length; j++) {
if(arr[j] == 0) zero++;
else one++;
if(zero == one)
maxLen = Math.max(maxLen, j - i + 1);
}
}
System.out.println("Input: [0,1,0,1,1,1,0]");
System.out.println("Output: " + maxLen);
}
}
Python
arr = [0,1,0,1,1,1,0]
n = len(arr)
maxLen = 0
for i in range(n):
zero = one = 0
for j in range(i, n):
if arr[j] == 0:
zero += 1
else:
one += 1
if zero == one:
maxLen = max(maxLen, j - i + 1)
print("Input: [0,1,0,1,1,1,0]")
print("Output:", maxLen)
JavaScript
let arr = [0,1,0,1,1,1,0];
let maxLen = 0;
for (let i = 0; i < arr.length; i++) {
let zero = 0, one = 0;
for (let j = i; j < arr.length; j++) {
if (arr[j] === 0) zero++;
else one++;
if (zero === one)
maxLen = Math.max(maxLen, j - i + 1);
}
}
console.log("Input: [0,1,0,1,1,1,0]");
console.log("Output:", maxLen);
C#
using System;
class Program {
static void Main() {
int[] arr = {0,1,0,1,1,1,0};
int maxLen = 0;
for(int i = 0; i < arr.Length; i++) {
int zero = 0, one = 0;
for(int j = i; j < arr.Length; j++) {
if(arr[j] == 0) zero++;
else one++;
if(zero == one)
maxLen = Math.Max(maxLen, j - i + 1);
}
}
Console.WriteLine("Input: [0,1,0,1,1,1,0]");
Console.WriteLine("Output: " + maxLen);
}
}
Final Output
Input: [0,1,0,1,1,1,0]
Output: 4
Approach 2: Prefix Sum + Hash Map (Optimal)
Idea
- Convert 0 → -1
- Use prefix sum
- If same prefix sum appears again, subarray between them has sum 0
Algorithm
- Create map: prefixSum → first index
- Initialize sum = 0, maxLen = 0
- Traverse array:
- If element is 0, add -1, else +1
- If sum == 0, update maxLen = i + 1
- If sum exists in map:
- Update maxLen = max(maxLen, i - map[sum])
- Else store sum → i
Time & Space Complexity
- Time: O(n)
- Space: O(n)
C
#include
int main() {
int arr[] = {0,1,0,1,1,1,0};
int n = 7;
int maxLen = 0, sum = 0;
int hash[2001];
for(int i = 0; i < 2001; i++) hash[i] = -2;
hash[1000] = -1; // sum = 0 at index -1
for(int i = 0; i < n; i++) {
sum += (arr[i] == 0 ? -1 : 1);
if(hash[sum + 1000] != -2) {
int len = i - hash[sum + 1000];
if(len > maxLen) maxLen = len;
} else {
hash[sum + 1000] = i;
}
}
printf("Input: [0,1,0,1,1,1,0]\n");
printf("Output: %d\n", maxLen);
return 0;
}
C++
#include
#include
using namespace std;
int main() {
int arr[] = {0,1,0,1,1,1,0};
int n = 7;
unordered_map mp;
int sum = 0, maxLen = 0;
mp[0] = -1;
for(int i = 0; i < n; i++) {
sum += (arr[i] == 0 ? -1 : 1);
if(mp.count(sum))
maxLen = max(maxLen, i - mp[sum]);
else
mp[sum] = i;
}
cout << "Input: [0,1,0,1,1,1,0]" << endl;
cout << "Output: " << maxLen << endl;
return 0;
}
Java
import java.util.HashMap;
public class LongestSubarray01Optimal {
public static void main(String[] args) {
int[] arr = {0,1,0,1,1,1,0};
HashMap map = new HashMap<>();
int sum = 0, maxLen = 0;
map.put(0, -1);
for(int i = 0; i < arr.length; i++) {
sum += (arr[i] == 0 ? -1 : 1);
if(map.containsKey(sum))
maxLen = Math.max(maxLen, i - map.get(sum));
else
map.put(sum, i);
}
System.out.println("Input: [0,1,0,1,1,1,0]");
System.out.println("Output: " + maxLen);
}
}
Python
arr = [0,1,0,1,1,1,0]
sum = 0
maxLen = 0
mp = {0: -1}
for i in range(len(arr)):
sum += -1 if arr[i] == 0 else 1
if sum in mp:
maxLen = max(maxLen, i - mp[sum])
else:
mp[sum] = i
print("Input: [0,1,0,1,1,1,0]")
print("Output:", maxLen)
JavaScript
let arr = [0,1,0,1,1,1,0];
let map = new Map();
let sum = 0, maxLen = 0;
map.set(0, -1);
for (let i = 0; i < arr.length; i++) {
sum += (arr[i] === 0 ? -1 : 1);
if (map.has(sum))
maxLen = Math.max(maxLen, i - map.get(sum));
else
map.set(sum, i);
}
console.log("Input: [0,1,0,1,1,1,0]");
console.log("Output:", maxLen);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {0,1,0,1,1,1,0};
Dictionary map = new Dictionary();
int sum = 0, maxLen = 0;
map[0] = -1;
for(int i = 0; i < arr.Length; i++) {
sum += (arr[i] == 0 ? -1 : 1);
if(map.ContainsKey(sum))
maxLen = Math.Max(maxLen, i - map[sum]);
else
map[sum] = i;
}
Console.WriteLine("Input: [0,1,0,1,1,1,0]");
Console.WriteLine("Output: " + maxLen);
}
}
Final Output
Input: [0,1,0,1,1,1,0]
Output: 4
Summary
- Brute force is intuitive but slow
- Prefix sum + hashing is optimal and interview-preferred
- Conversion trick (0 → -1) is the core insight
- Solves in one pass with O(n) time
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
