Queries on a Permutation With Key

Medium
1083.

Queries on a Permutation With Key

Queries on a Permutation With Key is a medium coding problem on arrays, simulation and binary indexed tree, asked in Amazon, Google and Oracle interviews.

Start with the permutation P = [1, 2, 3, …, m]. For each value in queries, in order:

  • record its current 0-based index in P;
  • move it to the front of P, leaving the relative order of everything else unchanged.

Return the recorded indices.

Example 1

Input
queries = [3,1,2,1], m = 5
Output
[2,1,2,1]
Explanation
`P` becomes `[3,1,2,4,5]`, `[1,3,2,4,5]`, `[2,1,3,4,5]`, `[1,2,3,4,5]`.

Example 2

Input
queries = [4,1,2,2], m = 4
Output
[3,1,2,0]
Explanation
The last query is already at the front.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} queries
 * @param {number} m
 * @return {number[]}
 */
var processQueries = function(queries, m) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Queries on a Permutation With Key — Problem & Solution

Queries on a Permutation With Key solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Queries on a Permutation With Key is a medium coding problem on arrays, simulation and binary indexed tree, asked in Amazon, Google and Oracle interviews.

Problem statement

Start with the permutation P = [1, 2, 3, …, m]. For each value in queries, in order:

  • record its current 0-based index in P;
  • move it to the front of P, leaving the relative order of everything else unchanged.

Return the recorded indices.

Example 1

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1]
Explanation: `P` becomes `[3,1,2,4,5]`, `[1,3,2,4,5]`, `[2,1,3,4,5]`, `[1,2,3,4,5]`.

Example 2

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]
Explanation: The last query is already at the front.

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

Hints for Queries on a Permutation With Key

  1. Hint 1

    At these sizes a direct simulation of the list is fast enough.

  2. Hint 2

    Find the value, record its index, remove it, and put it back at the front.

  3. Hint 3

    The scalable version keeps positions in a Fenwick tree and prepends into a reserved prefix.

How to solve Queries on a Permutation With Key

Simulate the list directly: scan for the queried value, record its index, then move it to the front. With m and the query count both at most 1000, the O(m) work per query is comfortable.

Approach

  1. Build P = [1..m].
  2. For each query, scan for its position and record it.
  3. Remove the value from that position and insert it at index 0.

Why it works

The quadratic simulation is the right answer at these bounds and is easy to get exactly right, which matters because the index is 0-based and recorded before the move. The Fenwick-tree solution exists for the same problem at scale: reserve m empty slots in front, keep each value's slot, and count the occupied slots before it to get the index in O(log m).

Complexity

  • Time — O(q · m)
  • Space — O(m)

Pitfalls

  • The index is recorded before the value is moved, not after.
  • Indices are 0-based.
  • Everything else keeps its relative order — only the queried value jumps.

Reference solution

Python

from typing import List

def processQueries(queries: List[int], m: int) -> List[int]:
    perm = list(range(1, m + 1))
    out = []
    for q in queries:
        idx = perm.index(q)
        out.append(idx)
        perm.pop(idx)
        perm.insert(0, q)
    return out

Java

public static int[] processQueries(int[] queries, int m) {
    List<Integer> perm = new ArrayList<>();
    for (int i = 1; i <= m; i++) perm.add(i);
    int[] out = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int idx = perm.indexOf(queries[q]);
        out[q] = idx;
        perm.remove(idx);
        perm.add(0, queries[q]);
    }
    return out;
}

C++

vector<int> processQueries(vector<int>& queries, int m) {
    vector<int> perm;
    for (int i = 1; i <= m; i++) perm.push_back(i);
    vector<int> out;
    for (int q : queries) {
        int idx = 0;
        while (perm[idx] != q) idx++;
        out.push_back(idx);
        perm.erase(perm.begin() + idx);
        perm.insert(perm.begin(), q);
    }
    return out;
}

JavaScript

var processQueries = function(queries, m) {
    var perm = [], i;
    for (i = 1; i <= m; i++) perm.push(i);
    var out = [];
    for (var q = 0; q < queries.length; q++) {
        var idx = 0;
        while (perm[idx] !== queries[q]) idx++;
        out.push(idx);
        perm.splice(idx, 1);
        perm.unshift(queries[q]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays