Queries on a Permutation With Key — Medium Problem & Solution

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,…

Difficulty: Medium
Topics: Arrays, Simulation, Binary Indexed Tree
Asked at: Amazon, Google, Oracle
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Build P = [1..m].
For each query, scan for its position and record it.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue