I have an array
a of values +1 and -1 in random order, and a separate array
s which is initialised with 0 in every position. I run through the array from left to right. At every index
i, I add the value of
s, s, ... , s[i-1], s[i]. And at every index
i, after doing the previous operation, I want to return the rightmost index in the range
[0, i] with value 0. If no such index exists, I'll return some invalid number like -1.
The adding operation can be done using a Fenwick tree. But I have no clue to find the rightmost index in logarithmic complexity. I'm trying to do the entire process in
O(nlogn) complexity. Any idea would be much appreciated, thanks!