[LeetCode 1409] Queries on a Permutation with Key

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

Because input size is only up to N = 10^3, a O(N^2) solution is sufficient enough in a contest. We can either use a hash map to keep each number's relative position and update the entire map after each query in O(N) time. (All smaller relative orders need to add 1). Or we keep a fixed sized array and do swaps for each query, after each query we do a 2-step reverse to get the correct ordering in O(N) time. The implementation of this swapping and reversing is fairly straightforward.

class Solution {
    public int[] processQueries(int[] q, int m) {
        int[] v = new int[m];
        for(int i = 0; i < m; i++) {
            v[i] = i + 1;   
        }
        int[] ans = new int[q.length];
        for(int i = 0; i < q.length; i++) {
            int j = 0;
            for(; j < m; j++) {
                if(q[i] == v[j]) {
                    break;
                }
            }
            ans[i] = j;
            int temp = v[0];
            v[0] = v[j];
            v[j] = temp;
            reverse(v, 1, j - 1);
            reverse(v, 1, j);
        }
        return ans;
    }
    private void reverse(int[] v, int i, int j) {
        while(i < j) {
            int temp = v[i];
            v[i] = v[j];
            v[j] = temp;
            i++;
            j--;
        }
    }
}

If we tight the given constraints to N = 10^5, then our O(N^2) algorithm is inefficient to fit in a contest time limit. 

The bottleneck here is that it takes O(N) solution to either find a position or do the adjusting right after each query. This is essentially a dynamic look up then update problem. This should be a hint for some dynamic data structures such as Binary Indexed Tree. 

Indeed, if we think of getting a query value V's position as finding out the total number of elements that currently appear before V. A query now becomes range sum from the beginning index to V's index - 1 inclusive.

The algorithm is as follows.

1. Create a binary indexed tree of size m * 2 + 1. (+1 for 1 indexed; the extra m slots are buffering zone for the queries). Initally 1 to m are added to index m + 1 to m * 2. 

2. Create a number to its current index in BIT mapping. Initially 1 to m are indexed from m + 1 to m * 2. 

3. Go over the queries one at a time, and do the following:

a. use the current query value's BIT index map[queries[i]] to get the range sum of index [1, queries[i] - 1]. This is how many numbers are currently ahead of queries[i], hence its relative position.

b. update index map[queries[i]] to 0, representing there is no number in this index anymore.

c. update queries[i]'s BIT index mapping to the next available buffering slot(1 to m) from right to left. 

d. update new index map[queries[i]] to 1, representing there is a new number in this new index now.

class Solution {
    class BinaryIndexedTree {
        int[] ft;        
        BinaryIndexedTree(int n) {
            ft = new int[n];
        }        
        int rangeSum(int r) {
            int sum = 0;
            for(; r > 0; r -= (r & (-r))) {
                sum += ft[r];
            }
            return sum;
        }        
        void update(int k, int v) {
            for(; k < ft.length; k += (k & (-k))) {
                ft[k] += v;
            }
        }
    }
    public int[] processQueries(int[] queries, int m) {
        BinaryIndexedTree bit = new BinaryIndexedTree(m * 2 + 1);
        int[] map = new int[m + 1];
        for(int i = 1; i <= m; i++) {
            map[i] = m + i;
        }
        for(int i = 1; i <= m; i++) {
            bit.update(m + i, 1);
        }
        int[] ans = new int[queries.length];
        for(int i = 0; i < queries.length; i++) {
            ans[i] = bit.rangeSum(map[queries[i]] - 1);
            bit.update(map[queries[i]], -1);
            map[queries[i]] = m - i;
            bit.update(map[queries[i]], 1);
        }
        return ans;
    }
}