We are given an array of integers and we need to find size of smallest subsegment such that after removing it all element in array are distinct .How to solve this problem using binary search in O(nlogn) ? I tried to read various submission's which use binary search but i couldn't understand them .
My attempt - I solve this problem in n^2logn using brute force but i want to know how to apply binary search to solve this problem in O(nlogn).
Link of Problem - https://codeforces.com/contest/1208/problem/B
Link of one of the solution implementing binary search -https://codeforces.com/contest/1208/submission/59494540
In the linked solution, the function check(int siz) returns true if it's possible to make all number unique by removing a subarray of size siz. It does this in O(n) time.
Since check(x) == true implies that check(y) == true for all y >= x, the main() function can do a binary search to find the smallest value of siz for which check(siz) == true, which is the solution to the problem.
If check(mid) == true, then the answer is not bigger than mid. If check(mid) == false, then the answer is bigger than mid.
The binary search requires O(log n) evaluations of check for a total of O(n log n) time.