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] 

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class QueriesPermutationWithKey {
    public static void main(String[] args) {
        int[] queries = { 3, 1, 2, 1 };
        int m = 5;
        int[] res = processQueries(queries, m);
        System.out.println(Arrays.toString(res));
    }
    static int find(int arr[], int m, int num) {
        int res = 0;
        for (int i = 0; i < m; i++)
            if (arr[i] == num) {
                res = i;
                break;
            }
        return res;
    }
    static int[] processQueries(int[] queries, int m) {
        int arr[] = new int[m];
        for (int i = 0; i < m; i++)
            arr[i] = i + 1;
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < queries.length; i++) {
            int pos = find(arr, m, queries[i]);
            res.add(pos);
            int temp = arr[pos];
            for (int j = pos; j > 0; j--)
                arr[j] = arr[j - 1];
            arr[0] = temp;
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
int find(int arr[], int m, int num)
{
    int res;
    for (int i = 0; i < m; i++)
        if (arr[i] == num)
        {
            res = i;
            break;
        }
    return res;
}
vector<int> processQueries(vector<int> &queries, int m)
{
    int arr[m];
    for (int i = 0; i < m; i++)
        arr[i] = i + 1;
    vector<int> res;
    for (int i = 0; i < queries.size(); i++)
    {
        int pos = find(arr, m, queries[i]);
        res.push_back(pos);
        int temp = arr[pos];
        for (int j = pos; j > 0; j--)
            arr[j] = arr[j - 1];
        arr[0] = temp;
    }
    return res;
}
int main()
{
    vector<int> queries = {3, 1, 2, 1};
    int m = 5;
    vector<int> res = processQueries(queries, m);
    cout << "[";
    for (int i = 0; i < res.size() - 1; i++)
        cout << res[i] << ",";
    cout << res[res.size() - 1] << "]";
    return 0;
}