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,XThe 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 ?
Looking for a dynamic programming solution
algorithms;dynamic programming