Having a look at the AC submissions, it appears that the solution to this problem is (n - length of longest increasing sub-sequence). But how does it handle the cases like
array : 3 1 2 3
The length of longest increasing sub-sequence is 3. But we can not replace 3 by 0 as it needs to be a positive integer. So, how is the answer 1 for this case ?
Simply finding the longest increasing subsequence will give wrong answer. To get proper answer you need to find the length of the longest strictly increasing subsequence only among all elements having the property that val[i] - i >= 0 for all i from 1…n . simple sequence satisfying this property is 1 2 3 4 … n. The first element has to be greater than or equal to 1, 2nd >= 2 and so on. Hence you need to make an array of elements satisfying this property(val[i] - i >= 0) and find LIS of these elements. Answer will be n - this_length.
P.S. I haven’t actually solved this question but i am sure this algorithm is correct.