# 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

## 2 Answers

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.

Truth be told, you'll probably need some big data sets for it to be worthwhile doing anything but invoking your language's builtin sort and taking a slice.

It does not look like DP would be of much use to solve your problem, because it does not exhibit the optimal substructure property.

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.