Widest Window With Equal Tallies

Medium

Two sensors log every minute whether they fired (1) or not (0). Their logs are the arrays first and second of equal length. Find the longest window of consecutive minutes [i, j] (i ≤ j) in which both sensors fired the same number of times, meaning the sum of first[i..j] equals the sum of second[i..j]. Return the length of that window, j - i + 1, or 0 if no such window exists.

Example 1

first=[1, 0, 1, 1, 0], second=[0, 1, 1, 0, 0] → 4

Window 0–3: first has 1 + 0 + 1 + 1 = 3 ones and second has 0 + 1 + 1 + 0 = 2, so it does not work. Window 1–4 gives 0 + 1 + 1 + 0 = 2 and 1 + 1 + 0 + 0 = 2, which match, length 4. The whole window 0–4 gives 3 against 2.

Example 2

first=[1, 1], second=[0, 0] → 0

Every window has more ones in first than in second, so the answer is 0.

Example 3

first=[0, 1, 0], second=[1, 0, 1] → 2

Constraints

1 ≤ n ≤ 10⁵, where n = len(first) = len(second)
first[i] and second[i] are 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Prefix Sum

Similar problems

Longest Run with a Given Sum Medium A Stretch Divisible by k Medium As Many Heads as Tails Medium Stretches With an Exact Total Medium Windows With an Exact Alarm Count Medium

Input

first=[1, 0, 1, 1, 0], second=[0, 1, 1, 0, 0]

Expected

Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.