Practice › Hashing & Two Pointers
Longest Subarray with Equal 0s and 1s
Medium · Hashing & Two Pointers · Asked at Amazon, Microsoft, Paytm, Morgan Stanley
The array contains only 0s and 1s. Print the length of the longest subarray with an equal number of 0s and 1s (0 if there is none).
Input
First line: n. Second line: n space-separated integers.
Output
The maximum length.
Constraints
- 1 ≤ n ≤ 10^5
- a[i] ∈ {0, 1}
Replace 0 by −1: you need the longest subarray with sum 0. Store the first index of every prefix sum.
Example 1
Input
3 0 1 0
Output
2
Example 2
Input
3 1 1 1
Output
0
Hints
- Treat 0 as −1 and 1 as +1. A subarray with equal counts has sum 0.
- Two equal prefix sums at indices j < i mean the subarray (j, i] sums to 0. Store the first index where each prefix sum appears.
Approach
Walk the array with a running balance (+1 for 1, −1 for 0). Keep first[balance] = the earliest index where that balance occurred, with first[0] = -1. At index i, if the balance was seen before, the subarray after that earliest index is balanced: candidate length i − first[balance]. Only the first occurrence is stored because it gives the longest subarray.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_map<int, int> first;
first[0] = -1;
int bal = 0, best = 0, x;
for (int i = 0; i < n; i++) {
cin >> x;
bal += x ? 1 : -1;
if (first.count(bal)) best = max(best, i - first[bal]);
else first[bal] = i;
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1:]
first = {0: -1}
bal = best = 0
for i, x in enumerate(a):
bal += 1 if x else -1
if bal in first:
best = max(best, i - first[bal])
else:
first[bal] = i
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Map<Integer, Integer> first = new HashMap<>();
first.put(0, -1);
int bal = 0, best = 0;
for (int i = 0; i < n; i++) {
bal += sc.nextInt() == 1 ? 1 : -1;
if (first.containsKey(bal)) best = Math.max(best, i - first.get(bal));
else first.put(bal, i);
}
System.out.println(best);
}
}Solve Longest Subarray with Equal 0s and 1s online · All practice problems