Looking for a dynamic programming solution

Given a sequence of integers in range 1 to n. Each number can appear at most once. Let there be a symbol X in the sequence which means remove the minimum element from the list. There can be an arbitrarily number of X in the sequence. Example: 1,3,4,X,5,2,X The output is 1,2.

We need to find the best way to perform this operation.

The solution I have been thinking is:

Scan the sequence from left to right and count number of X which takes O(n) time. Perform partial sorting and find the k smallest elements (k = number of X) which takes O(n+klogk) time using median of medians.

Is there a better way to solve this problem using dynamic programming or any other way ?

• Does X mean "remove the smallest element so far", or is it a global operation? For example, is 1,3 the answer to 1,3,4,X,5,X,2? – dasblinkenlight Sep 30 '12 at 13:41
• @dasblinkenlight X is the smallest element seen so far – krammer Sep 30 '12 at 16:01
• What if you have something like 1,X,X? – Winston Ewert Oct 5 '12 at 0:33
• @WinstonEwert I think the problem statement should have put a limit on number of X. i.e. n(X) <= number of elements seen so far or it should be specified that if no element exists, return null. – krammer Oct 5 '12 at 12:33