Link to the problem.
My idea is first grouping the array into sorted subarray, for example if the the array was [1, 5, 6, 2, 4, 7, 3]. We can group it into [[1, 5, 6], [2, 4, 7], ] so that each groups are sorted. Meaning for each group Gi with a length Ni, It is possible to remove Ni — 1 element from it. So if we all ways remove the larger one , the smallest element will left.
After this let minn be the smallest element in group0 (first sorted group), if there is an element greater than minn in group1, then update value of minn to the smallest element greater than minn in group1, else the answer is "NO". Then again there should be an element greater than (updated) minn in group2, and so on.... If there isn't such value then the answer is "NO".
In the above example, when array is [1, 5, 6, 2, 4, 7, 3], the groups will be [[1, 5, 6], [2, 4, 7], ]. First minn will be min(1, 5, 6) = 1. Then find the smallest element greater than 1 in group1 which is 2. Then smallest element greater than 2 in group2 will be 3, so the answer will be "YES". ...
Python Code : Here
Can someone tell me what is wrong in the approach or give a counter example?
Thanks in advance for devoting your time to read this!