Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Treat 0 as −1 and 1 as +1. A subarray with equal counts has sum 0.
  2. 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