We have an array of numbers 0 and 1. For every index R, we need to find the leftmost index L so that total number of 0's between L and R is more than 1's. We have to find the length (R-L+1). For example,
consider this array: 1 0 1 0 0 1 1
for the 2nd index, length is 1: 1 0 1 0 0 1 1
for the 3rd index, length is 0: 1 0 1 0 0 1 1
for the 4th index, length is 3: 1 0 1 0 0 1 1
for the 5th index, length is 5: 1 0 1 0 0 1 1
We have to find the length for every index. My question is, can it be done in linear time complexity? Or, what's the best time complexity to solve it? Please share your ideas! Thanks.
Here is an O(NlogN) solution. Let's replace all zeroes with -1 and multiply everything by -1. So in other words, we replace 1 with -1 and 0 with 1. It's easy to see that now we are looking for the longest subarray with positive sum which is a standard problem (I don't know any O(N) algo, maybe somebody can share it if he/she knows?). I will explain how to solve it logarithmically. Let P[i] be A[1]+A[2]+...+A[i] where A is the array with -1 and 1. Say we are at step i and the sum is P[i]. We are looking for the least j such that P[i]-P[j]>0 which means P[i]>P[j]. Let L[k] be the leftmost position of partial sum equal to k (initially filled with INF). At the current step we have ans[i]=i-min(L[-N],L[-(N+1)],...,L[0],...,L[P[i]-1])+1 and then we need to update L[P[i]]=min(L[P[i]],i). Negative indices can be handled by adding N+1 to each index. So, as it can be seen, we need a data structure that supports updating the element on a position and getting the minimum for a range, so segment tree or binary indexed tree will do the job! :)
We can modify your solution to change its complexity to O(N). Let's replace zeroes with 1 and ones with -1. Then let's create particle sums array S[N+1]: S[N]=0, S[i] = A[N-1] + A[N-2]+...+A[i]. Now we want to find such a minimal index k, that S[k] — S[i+1] is positive, for O(1).
For that let's create an array P[2*N+1] with indices from -N to N, where P[j]=k holds the first position k where we get particle sum S[k]=j. Then let's replace each P[j] with min(P[N], P[N-1],...,P[j]) because if the particle sum j is OK, the particle sum j+1 is OK too. We can do it for O(N).
To solve the problem for each current index i we need such an index k, that S[k] > S[i+1] and k <= i. This index is P[S[i+1]+1] — the minimal index, where the particle sum becomes > S[i+1]. So, for each position i answer is (i — P[S[i+1]+1] + 1) if P[S[i+1]+1] <= i and 0 otherwise.
Thank you very much! :)
Where can I find this problem?is there any link?