# 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`? Sep 30, 2012 at 13:41
• @dasblinkenlight X is the smallest element seen so far Sep 30, 2012 at 16:01
• What if you have something like `1,X,X`? Oct 5, 2012 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. Oct 5, 2012 at 12:33

Dynamic programming is unlikely to be helpful here. You've already got a `O(n log n)` solution, Dynamic programming tends to run more like `O(n^2)` or `O(n^3)`. (There are exceptions, but I wouldn't expect to find a better solution here.)
What you can look at using is a size-limited heap. Basically, use the heap to hold the `k` smallest values found so far. For each new value, compare with the highest value in the heap, and replace it if we've got a lower one.
The problem can be solved very efficiently with a priority queue: when you see a number, negate it, and add the result to the priority queue. When you see an `X`, dequeue the highest-priority number, and negate it again before adding it to the answer.