MasterFromLasVegas's blog

By MasterFromLasVegas, history, 8 days ago, In English,

I understood the solution in the editorial, and also the solution in with 2 pointers[having 2 pointers to point to last positions of 1,2 and 3].

How is it possible to solve this problem using binary search ?

can any one explain or point me to a submission ?

Thank you

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

80510798

Now we have to find the minimum window s.t. it contains all three-elements at least once. Minimum size of the window could be 3(left) and maximum size(right) could be n (size of array). Take three arrays (a1,a2,a3) each of size n+1 for storing the frequencies of 1,2,3 (like prefix sums). Apply binary search and you'll get a window size say "w"(mid), traverse the input array and at any index check if the frequency of elements(1,2,3) in that window (i to i+w-1) is > 0 or not (which can be done in O(1) using a1,a1,a3 arrays). If you find a solution for a particular windows size store it in some variable and move "right" to "mid -1" to find a window size smaller than current size and if not move "left" to "mid+1" to check for some window of size greater than "w".

Complexity is O(nlogn)

»
8 days ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

My submission using BS

80640431