How do I select all elements in a list that are out-of-order?

Question

This question arose from the discussion in the comments of this answer.

First, let's say it's quite difficult to define what out-of-order is. Taking the example Pavel Shved gave, in the list [1,5,10,2,3,4,5,6,7,8,9,10,11] we can "clearly" see that 5 and 10 (indices 1 and 2) are out of order. But a naïve algorithm that simply checks some kind of sorted list invariant would not point those out.

• checking a[i-1]<=a[i] for all 0<i<=N would yield the element at index 3 (which is 2);

• checking a[j]<=a[i] for all 0<=i<=N and 0<=j<=i would yield all elements in indices 3 to 12;

My question is: can you think of an algorithm to solve this problem that yields the "correct answer" (i.e. indices 1 and 2)? If so, under what time and memory complexity would it run?

Answer 1

Probably the best approach to this would be to first find the longest increasing subsequence and then consider all elements not part of that sequence to be out of order. The algorithm provided on the linked page runs in O(n log n) time and uses O(n) space (in addition to that of the list itself).

Such an approach would definitely yield the correct answer for your example case, since the longest increasing subsequence would be the 1 through 11 sequence not including the extra 5 and 10.

Answer 2

How should the algorithm know which elements you consider out of order?

If the rule is "list[i+1] should always be list[i] + 1", then it would be easy, of course, just memorizing that after 1, the next element should be 2, select those in between and so on. But you need a precise rule for the algorithm to determine which elements are to be considered "out-of-order".