Given a number n, the initial list is (i.e. the initial list is sorted and contains elements from 0 to n-1):
[0, 1, 2, ... n - 1]
The input is a sequence of m numbers. For each number in the input, move the number to the front of the list, and print out the index of that number.
For example:
n = 5:
Input:
3 3 4 2
Output:
3 0 4 4
Explanation: Given n = 5, the initial list is
[0, 1, 2, 3, 4]
We first move 3 to the front. The index of 3 in the list is 3.
[3, 0, 1, 2, 4]
Then we move 3 again to the front. Because it is already in the front, the index is 0.
[3, 0, 1, 2, 4]
Then, we move 4 to the front. The index of 4 is 4.
[4, 3, 0, 1, 2]
Lastly, we move 2 to the front. The index of 2 is 4.
[2, 4, 3, 0, 1]
I implemented a O(mn) solution easily by linearly searching for the index of an element for every move-to-front. However, I can't think of a way to do this within the required time complexity O(m sqrt(n)).
I think maybe since we do not need to return the actual list after the move-to-front's, we can somehow leverage this to reduce the amount of work. Maybe some additional data structures might help?