Queries on a Permutation With Key: Simulate and Track

You are given an array queries and a positive integer m. Start with a permutation P = [1, 2, 3, ..., m]. For each queries[i], find the position of queries[i] in P, add that position to the result array, then move queries[i] to the beginning of P. Return the result array.

This is LeetCode 1409: Queries on a Permutation With Key. It tests whether you can carefully simulate an array operation that involves finding an element, recording its index, and shifting it to the front. The move-to-front pattern shows up in caching strategies, self-organizing lists, and compression algorithms.

Direct simulation works

The constraints are small: m and queries.length are both at most 1000. That means a brute-force simulation with O(n * m) time is perfectly fine. For each query, you scan P to find the element, record its index, remove it, and insert it at position 0. Python's list.index(), list.pop(), and list.insert() make this clean and readable.

The simulation approach:

1. Build P = [1, 2, 3, ..., m].
2. For each value in queries, call P.index(val) to find its position.
3. Append that position to the result.
4. Remove the element with P.pop(idx) and reinsert it at the front with P.insert(0, val).

That is the entire algorithm. No clever data structures, no tricky index math. Just simulate exactly what the problem describes.

Can we do better?

You could use a Binary Indexed Tree (Fenwick tree) to track positions and achieve O(n log n) time. The idea is to place the elements in an extended array where the front has room for elements to be moved, and use the BIT to count how many elements are before a given position. Each query becomes a point update and prefix sum query.

But for the given constraints (n, m up to 1000), the simulation runs in under a millisecond. The BIT approach is worth knowing for competitive programming, but in an interview you should reach for the simple simulation first, mention the optimization if asked, and move on.

The solution

def process_queries(queries: list[int], m: int) -> list[int]:
    P = list(range(1, m + 1))
    result = []
    for val in queries:
        idx = P.index(val)
        result.append(idx)
        P.pop(idx)
        P.insert(0, val)
    return result

Let's walk through what each piece does.

We initialize P as [1, 2, ..., m], the identity permutation. The result list will hold the answer.

For each value in queries, we find its current index in P using P.index(val). This is an O(m) scan, which is fine given the constraints. We append that index to result.

Then we perform the move-to-front operation: P.pop(idx) removes the element from its current position, and P.insert(0, val) places it at the beginning. This shifts all elements between index 0 and idx one position to the right.

The beauty of this problem is that the solution reads almost exactly like the problem statement. There is no gap between understanding the problem and writing the code.

Step-by-step walkthrough

Let's trace through queries = [3, 1, 2, 1] with m = 5. Watch how P changes after each query and how each position gets recorded.

Notice that when the same element is queried twice (like 1 appearing at queries[1] and queries[3]), its position in P depends on what happened between the two queries. After the first query for 1, it moved to the front. But then querying 2 pushed 2 to the front, shifting 1 to index 1. So the second query for 1 returns 1, not 0. The order of queries matters because each one reshuffles the permutation.

Complexity analysis

Time: O(n * m). We process n queries. For each query, P.index() scans up to m elements (O(m)), P.pop() shifts up to m elements (O(m)), and P.insert(0, val) shifts up to m elements (O(m)). Each query costs O(m) work, and there are n queries, giving O(n * m) total. With n and m both at most 1000, that is at most 1,000,000 operations.

Space: O(m). We store the permutation P of size m and the result array of size n. The permutation dominates if m is larger, but both are bounded by the input size.

Building blocks

1. Linear search for position

The pattern of scanning an array to find the index of a target value:

idx = P.index(val)

This is the simplest form of search. You walk through the array left to right until you find the element. It is O(n) per call, which is acceptable when the array is small or when the problem guarantees limited iterations. You will see this same pattern in problems like "Find the Index of the First Occurrence in a String" and any simulation problem where you need to locate an element before acting on it.

2. Move-to-front operation

The pattern of removing an element and reinserting it at the beginning of a list:

P.pop(idx)
P.insert(0, val)

This two-step operation is the core of self-organizing lists. Recently accessed items migrate toward the front, making repeated accesses faster. You will encounter this same pattern in LRU Cache (LeetCode 146), where the most recently used item moves to one end of a doubly-linked list. The data structure differs (linked list vs. array), but the idea is identical: promote recently accessed elements to reduce future lookup time.

Edge cases to watch for

• Single query: queries = [1], m = 1. The only element is already at index 0. Result is [0].
• Repeated queries for the same element: After the first access, the element is at index 0. Every subsequent access for the same element (with no intervening queries for other elements) returns 0.
• Querying elements in reverse order: queries = [m, m-1, ..., 1]. Each query finds the element at the end of the remaining permutation, producing the largest possible indices.
• All queries for the same value: queries = [k, k, k, ...]. The first query returns k-1 (0-indexed position in the initial permutation). Every subsequent query returns 0 because the element is already at the front.
• m equals 1: The permutation is [1]. Every query must be for value 1, and the result is always [0, 0, ..., 0].

From understanding to recall

You have seen how the move-to-front simulation works: find the element, record its index, pop it, insert at front. The code is short and maps directly to the problem statement. But under interview pressure, small details like whether index() is 0-based or 1-based, or whether you pop before or after recording the index, can trip you up.

Spaced repetition closes that gap. You practice writing the simulation loop from memory, verifying the order of operations (find, record, pop, insert), and tracing through an example to confirm correctness. After a few rounds, the move-to-front pattern becomes automatic. You read "move to the beginning" in a problem and the code writes itself.

Related posts

• Design Linked List - Move-to-front pattern in linked lists
• LRU Cache - Move-to-front as cache eviction strategy
• Shuffle an Array - Array permutation operations

CodeBricks breaks Queries on a Permutation With Key into its linear-search and move-to-front building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a simulation problem shows up in your interview, you do not hesitate. You just write it.