Abstract / Summary

Given a permutation and a key, repeatedly move the key to the front and record the position of a specified number after each move.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 84% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Indexed Tree
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method processQueries. The method receives a list of integer queries and an integer m that defines the initial permutation of numbers from 1 to m. For each query the method determines the current position of the queried value in the permutation, yields that position, and then moves the queried value to the front of the permutation. The use of a generator (yield) allows the caller to retrieve results one at a time without allocating an intermediate list.

Initialization of the Permutation

The first executable line inside the method constructs the initial permutation:

p = list(range(1, m + 1))

A list p is created containing the sequence [1, 2, …, m]. This list represents the mutable ordering that will be updated after each query.

Processing Each Query

The core of the algorithm is a for loop that iterates over the supplied queries:

for q in queries:
    pos = p.index(q)
    yield pos
    p.pop(pos)
    p.insert(0, q)

Locating the Queried Value

The statement pos = p.index(q) searches the current permutation for the value q and records its zero-based index. This step determines the answer that will be emitted for the current query.

Emitting the Position

Immediately after locating the index, the method yields the position:

yield pos

Because yield is used, the method behaves as a generator. The caller receives each position as soon as it is computed, which can be advantageous when the result set is large.

Updating the Permutation

Two list operations follow the yield:

p.pop(pos)
p.insert(0, q)

p.pop(pos) removes the element at the previously found index, effectively extracting the queried value from its current location. p.insert(0, q) then inserts that same value at the front of the list, ensuring that the next occurrence of the same query will be found at position 0. This pair of operations maintains the required “move-to-front” behavior.

Edge Cases Handled by the Code

When a query refers to the element that is already at the front of the permutation, p.index(q) returns 0. The subsequent pop removes the first element and insert places it back at the front, leaving the list unchanged. The algorithm therefore correctly yields 0 for such queries without any special-case logic.

If a query targets the last element of the permutation, p.index(q) yields the maximal valid index. The pop operation removes the tail element, and the insert operation moves it to the front, correctly reflecting the required reordering.

Repeated queries are naturally supported. After the first occurrence of a value, the value resides at index 0. Any subsequent occurrence will therefore produce a yielded position of 0, and the list update steps will effectively be a no-op, preserving the invariant that the most recently queried element stays at the front.

The code also works when queries is empty. The for loop simply does not execute, and the generator produces no output, which is a valid behavior for an empty input sequence.

Performance Optimizations Present in the Implementation

The algorithm relies on Python’s built-in list methods (index, pop, insert). These methods are implemented in C and therefore execute faster than equivalent pure-Python loops. By using list.index the code avoids writing an explicit search loop, delegating the work to a highly optimized routine.

The generator pattern (yield) eliminates the need to allocate a separate list to hold all results. This reduces memory pressure, especially when the number of queries is large, because each result is produced and can be consumed immediately.

The combination of pop followed by insert at the front ensures that the list remains contiguous in memory, allowing subsequent operations to benefit from cache locality. Although both operations involve shifting elements, performing them in sequence leverages the internal optimizations of the list data structure.

Overall, the implementation balances clarity with the use of efficient built-in operations, delivering a solution that is both concise and performant for the problem’s requirements.

Imagine a row of numbered blocks sitting on a shelf, starting with one and going all the way up to a number like ten. There is a special list of request cards that tell which block to pick up next. When a card names a specific number, the shelf is searched to find exactly where that block is hiding. Once that block is found, its position is noted down on a piece of paper. Then, that block is taken out of its spot and moved all the way to the very front of the shelf, pushing all the other blocks down to make space. This keeps repeating for every single card in the list until every request has been handled and every block has had a chance to move to the front.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim						C
	everthis			JS
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality