3
$\begingroup$

Here is my approach

First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here: http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

Let's suppose the longest subsequence has $L$ elements. Then if $L < N - M$, there isn't any way to solve the problem since there's no subsequence of length $N - M$ that's still sorted.

Otherwise, just remove the $N - L$ elements that aren't in the subsequence, and then remove more at random until exactly M total have been removed. In all this is an $N \log N$ algorithm.

I want to know, is there any more efficient algorithm (i.e. $O( N)$ ) to solve this problem ?

$\endgroup$
2
$\begingroup$

You can adapt the algorithm described in Wikipedia so that it runs in time $O(N\log (N-M))$ if you're only interested in increasing sequences of length at most $N-M$. Judging by the existence of an $N\log N$ lower bound for the general case, $O(N\log(N-M))$ might be optimal. (Your problem is equivalent to the decision problem of whether there exists a non-decreasing subsequence of length $N-M$; this can be reduced to strictly increasing subsequences by adding appropriate $\epsilon$s.)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.