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.
