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.
- 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^31 <= queries.length <= m1 <= queries[i] <= m
Hints for Queries on a Permutation With Key
Hint 1
At these sizes a direct simulation of the list is fast enough.
Hint 2
Find the value, record its index, remove it, and put it back at the front.
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
- 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 outJava
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