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 ?

  • 1
    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
    – krammer
    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.
    – krammer
    Oct 5, 2012 at 12:33

2 Answers 2


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.