Given 2 binary arrays A and B i.e. containing only 0s and 1s each of size N.
Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum possible value.
Solution:
This is same as finding the longest subarray with sum zero in the array C[i] = A[i] - B[i].
Prefix sums + hashtable should give it.
Complexity:
time - O(n)Links and credits:
space - O(n)
http://www.careercup.com/question?id=25036663
No comments:
Post a Comment