Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 ?

share|improve this question
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? –  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

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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