Queries On A Permutation With Key - Leetcode Solution

The Queries on a Permutation with Key problem on LeetCode asks us to implement a class called Solution that has the following two methods:

1. void processQueries(vector<int>& queries, int m): This method takes in a vector of integers called queries and an integer called m. It should process each query in the queries vector as follows:
   • Given the permutation of the integers 1 to m as p = [1, 2, ..., m], find the index of the query element in p.
   • Remove the query element from p and insert it at the front of p.
   • Push the index of the query element into a result vector.
2. vector<int> processQueries(vector<int>& queries, int m): This method should return the result vector.

Here's a step-by-step solution to this problem:

1. Implement a class called Solution that contains an integer vector called p to represent the permutation of numbers 1 to m, and an integer vector called result to store the results of processing each query.

class Solution {
private:
    vector<int> p;
    vector<int> result;
public:
    Solution(){}
};

2. Implement the processQueries method by first initializing the permutation p with the numbers 1 to m.

void processQueries(vector<int>& queries, int m) {
    // Initialize p with numbers 1 to m
    for(int i=1; i<=m; i++){
        p.push_back(i);
    }
}

3. Loop through the queries vector and for each query:
   • Find the index of the query element in p
   • Remove the query element from p using erase method and insert it at the front using insert method.
   • Push the index of the query element into the result vector.

void processQueries(vector<int>& queries, int m) {
    for(int i=1; i<=m; i++){
        p.push_back(i);
    }
    for(int i=0; i<queries.size(); i++){
        int idx = find(p.begin(), p.end(), queries[i]) - p.begin();
        result.push_back(idx);
        p.erase(p.begin() + idx);
        p.insert(p.begin(), queries[i]);
    }
}

4. Implement the getResults method to return the result vector.

vector<int> getResults(){
    return result;
}

The complete solution of the Queries on a Permutation with Key problem on LeetCode:

class Solution {
private:
    vector<int> p;
    vector<int> result;
public:
    Solution(){}
    
    void processQueries(vector<int>& queries, int m) {
        for(int i=1; i<=m; i++){
            p.push_back(i);
        }
        for(int i=0; i<queries.size(); i++){
            int idx = find(p.begin(), p.end(), queries[i]) - p.begin();
            result.push_back(idx);
            p.erase(p.begin() + idx);
            p.insert(p.begin(), queries[i]);
        }
    }
    
    vector<int> getResults(){
        return result;
    }
};

1