Longest Span with Same Sum

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given two binary arrays, a1 and a2, of the same size N. A binary array is one that contains only 0s and 1s.

Your task is to find the length of the longest contiguous subarray (span) [i...j] where the sum of its elements in a1 is equal to the sum of its elements in a2.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'N', the size of the arrays.

The second line contains 'N' space-separated integers (0s and 1s) for array a1.

The third line contains 'N' space-separated integers (0s and 1s) for array a2.

Output Format:

Print a single integer representing the length of the longest span with an equal sum.

If no such span exists, print 0.

Note:

The condition sum(a1[i...j]) == sum(a2[i...j]) can be rewritten as sum(a1[i...j]) - sum(a2[i...j]) == 0.

This is equivalent to sum(a1[k] - a2[k]) == 0 for k from i to j.

The problem can be transformed by creating a temporary difference array diff[k] = a1[k] - a2[k]. The problem is now to find the longest subarray in diff that sums to zero.

This subproblem can be solved efficiently in O(N) time using a hash map to store prefix sums.

Sample Input 1:

6
0 1 0 0 0 0
1 0 1 0 0 1

Sample Output 1:

Explanation for Sample 1:

1.  Create the difference array: `diff = {-1, 1, -1, 0, 0, -1}`.
2.  Find the longest subarray in `diff` that sums to 0.
3.  The subarray from index 1 to 4 is `{1, -1, 0, 0}`, and its sum is 0.
4.  The length of this subarray is `4 - 1 + 1 = 4`.

Sample Input 2:

3
0 0 0
1 1 1

Sample Output 2:

Explanation for Sample 2:

Difference array `diff = {-1, -1, -1}`. No subarray in this array sums to 0.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= N <= 10^5
`a1[i]` and `a2[i]` are either 0 or 1.

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Longest Span with Same Sum

Console