I have an array A[0..N-1] containing N elements and a list containing M indexes. Each index in the list corresponds to an element in the array. For example, an index of 0 corresponds to A[0], an index of 1 corresponds to A[1]

I want to process the list sequentially from the first index to the last index as follows:
For the current index i,

1. if A[i] is not taken, then A[i] will be taken.
2. if A[i] is taken, then the smallest j > i where A[j] is not taken will be chosen and A[j] will be taken. If there is no such element, output -1

I want to output an array B of length M where B[i] denotes the index of element taken. I wonder how do I do it in linear complexity. (i.e. O(N) or O(M)). What data structure could be used?

CodePudding user response：

Here is a suggestion for an O(M*logM) algorithm.

At the start, insert all M i-indexes of the list into a sorted tree allowing doubles. The steps become,

1. If A[i] is not taken, then take A[i]. Remove the i from the tree.
2. If A[i] is taken, then the smallest j > i where A[j] is not taken will be chosen and A[j] will be taken. The smallest j>i is readily available after i in the tree. If there is no such j, output -1. Otherwise, remove the j from the tree.