Queries on a Permutation With Key

Array from 1 to M, input query array, find each element’s index, then move it to the front. M won’t exceed 1000.

Brute Force

The size limit on M lets us use brute force to traverse and move elements.

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> a(m);
        a[0]=1;
        vector<int> res;
        for(int i=1;i<a.size();++i) {
            a[i]=a[i-1]+1;
        }
        
        for(int i=0;i<queries.size();++i) {
            int target=queries[i];
            int j;
            for(j=0;j<a.size();++j) {
                if (a[j] == target) {
                    res.push_back(j);
                    break;
                }
            }
            for(int k=j;k>0;--k) {
                a[k]=a[k-1];
            }
            a[0]=target;
        }
        return res;
    }
};

Prefix Sum Approach

Use a Fenwick tree to speed up prefix sum queries. Treat the result as prefix sums of elements. Moving elements requires updating the tree with additions or subtractions.

class Fenwick {
public:
    Fenwick(int n) : val(n) {}
    
    int query(int i) {
        int s=0;
        while(i>0) {
            s+=val[i];
            i-=i&-i;
        }
        return s;
    }
    
    void update(int i, int delta) {
        while(i<val.size()) {
            val[i]+=delta;
            i+=i&-i;
        }
    }
    
    vector<int> val;
};

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        Fenwick tree((m<<1)+1);
        vector<int> pos(m+1);
        vector<int> res;
        
        for(int i=1;i<=m;++i) {
            pos[i]=i+m;
            tree.update(i+m, 1);
        }
        
        for(int q : queries) {
            res.push_back(tree.query(pos[q]-1));
            tree.update(pos[q], -1);
            pos[q]=m--;
            tree.update(pos[q], 1);
        }
        return res;
    }
};

#tree #prefix-sum

Powers of N: Two Ways to Check Reconstructing Binary Trees from Traversal Sequences