Longest subarray with more 0 than 1

Revision en1, by helpme, 2015-10-27 22:51:42

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English helpme 2015-10-27 22:51:42 684 Initial revision (published)