### MasterFromLasVegas's blog

By MasterFromLasVegas, history, 8 days ago, ,

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

• 0

 » 8 days ago, # | ← Rev. 4 →   0 80510798Now 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 →   +3 My submission using BS80640431