Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:
In the beginning, you have the permutation P=[1,2,3,...,m].
For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].
Return an array containing the result for the given queries.
Example 1:
Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1]
Explanation: The queries are processed as follow:
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5].
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5].
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5].
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5].
Therefore, the array containing the result is [2,1,2,1].
Example 2:
Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]
Example 3:
Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]
Constraints:
1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m
Solutions
Solution 1: Simulation
The problem's data scale is not large, so we can directly simulate it.
The Binary Indexed Tree (BIT), also known as the Fenwick Tree, efficiently supports the following two operations:
Point Updateupdate(x, delta): Adds a value delta to the element at position x in the sequence.
Prefix Sum Queryquery(x): Queries the sum of the sequence over the interval [1,...,x], i.e., the prefix sum at position x.
Both operations have a time complexity of $O(\log n)$.
The fundamental functionality of the Binary Indexed Tree is to count the number of elements smaller than a given element x. This comparison is abstract and can refer to size, coordinate, mass, etc.
For example, given the array a[5] = {2, 5, 3, 4, 1}, the task is to compute b[i] = the number of elements to the left of position i that are less than or equal to a[i]. For this example, b[5] = {0, 1, 1, 2, 0}.
The solution is to traverse the array, first calculating query(a[i]) for each position, and then updating the Binary Indexed Tree with update(a[i], 1). When the range of numbers is large, discretization is necessary, which involves removing duplicates, sorting, and then assigning an index to each number.