2
$\begingroup$

I am interested in the following problem:

We are given an array of integers and we need to find the size of smallest subsegment such that after removing it all elements in the array are distinct.

How to solve this problem using binary search in $O(n\log n)$? I tried to read various submissions which use binary search, for example this one, but I couldn't understand them.

My attempt - I solved this problem in $O(n^2\log n)$ using brute force, but I want to know how to apply binary search to solve this problem in $O(n\log n)$.

$\endgroup$
0
$\begingroup$

The idea is that you can check whether the answer is at most some value $m$ in time $O(n)$. Applying binary search on $m$, you obtain an $O(n\log n)$ solution.

How do you check whether the answer is at most $m$ in time $O(n)$? The idea is to slide a window of length $m$ across your array. If at some point all elements outside the window are distinct, then we are done.

How do we implement this sliding algorithm? Let $A$ be the original array. We initialize an array $M$ which contains the histogram of the elements in $A_{m+1},\ldots,A_n$, as well as the number of distinct elements $x$. If $x = n-m$ then we are done. Otherwise, we modify $M$ to contain the histogram of $A_1,A_{m+2},\ldots,A_n$:

  • We remove one copy of the element $A_{m+1}$ from $M$. If the new count of this element is $0$, then we decrease $x$.
  • We add one copy of the element $A_1$ to $M$. If the new count of this element is $1$, then we increase $x$.

In this way, we can update $M$ in time $O(1)$ per shift.

The solution you link to does all this, apart from maintaining $x$; this is done automatically by the C++ map data structure.

Another point is the time complexity of this solution, which might depend on your exact computation model.

$\endgroup$
  • $\begingroup$ I did not understood applying binary search part of the submission .I mean i know binary search on sorted array but how binary search is applied on m i didn't understood . $\endgroup$ – user108499 Aug 30 at 17:24
  • $\begingroup$ That’s a great thing for you to work out. $\endgroup$ – Yuval Filmus Aug 30 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy