Convert a given array of integers to a sorted one, by deleting the minimum number of elements

Question

I am working on the following problem:

I have to convert a given array of integers to a sorted one, by deleting the minimum number of elements.

For example: [3,5,2,10,11] will be sorted by deleting ‘2‘ : [3,5,10,11]. Or [3,6,2,4,5,7,7] will be sorted by deleting ‘3‘,’6‘ : [2,4,5,7,7] OR by deleting ‘6‘,’2‘ : [3,4,5,7,7] (both ways i remove 2 elements, that’s why they are both correct).

My thought was to keep a counter for each element to see how many conflicts it has with other elements. What i mean by conflicts: in the first example, numbers ‘3‘ and ‘5‘ have 1 conflict each (with the number ‘2‘) and number ‘2‘ has 2 conflicts (with numbers ‘3‘ and ‘5‘). So, after calculating the array of conflicts, i remove from the original array the element that has the max number of conflicts and i repeat for the remaining array until all elements have 0 conflicts.

This is not an efficient way though (in some cases that i havent thought it might also produce wrong results), so i was wondering if anyone could think of a better solution.

Answer 1

I believe this is just a cleverly disguised version of the longest increasing subsequence problem. If you delete the minimum number of elements to have a sorted sequence, what you're left with is the longest increasing subsequence of the original array. Accordingly, you can do the following:

1. Find the longest increasing subsequence (O(n log n) algorithms exist for this), then
2. Delete everything not in that subsequence.

Hope this helps!