Problem Description

You are given an array queries containing positive integers between 1 and m, and you need to process each query in order.

Initially, you have a permutation P = [1, 2, 3, ..., m].

For each query queries[i]:

1. Find the current position (0-indexed) of the value queries[i] in permutation P
2. Record this position as the result for this query
3. Move the element queries[i] from its current position to the beginning of permutation P

The task is to return an array containing the positions found for all queries.

For example, if m = 5 and queries = [3, 1, 2]:

• Initial P = [1, 2, 3, 4, 5]
• Query 1: Find 3 at position 2, move it to front → P = [3, 1, 2, 4, 5], result = 2
• Query 2: Find 1 at position 1, move it to front → P = [1, 3, 2, 4, 5], result = 1
• Query 3: Find 2 at position 2, move it to front → P = [2, 1, 3, 4, 5], result = 2
• Final answer: [2, 1, 2]

The solution simulates this process directly by maintaining the permutation list, finding the index of each query value, recording it, then removing and reinserting the element at the front.

Intuition

The problem asks us to track positions of elements as they get moved to the front of a list. The key observation is that we're essentially simulating a "move-to-front" data structure, where recently accessed elements are prioritized by placing them at the beginning.

Since we need to:

1. Find where an element currently is
2. Move it to the front
3. Track its position before moving

The most straightforward approach is to directly simulate these operations. We maintain the permutation as a list and perform the exact operations described: find the index, record it, remove the element, and insert it at position 0.

Why does simulation work here? Looking at the constraints (with m likely being reasonably small), the cost of operations like index(), pop(), and insert() on a list is acceptable. For each query, we perform:

• O(m) to find the element's position
• O(m) to remove it from its current position
• O(m) to insert it at the front

With n queries, this gives us O(n * m) time complexity, which is feasible for the problem's scale.

The beauty of this solution is its clarity - the code directly mirrors what the problem asks us to do, making it easy to understand and verify correctness. While more sophisticated data structures could optimize this further, the direct simulation is sufficient and keeps the implementation simple.

Solution Approach

The solution uses direct simulation to process each query, maintaining the permutation as a Python list.

Initial Setup:

• Create the initial permutation p = [1, 2, 3, ..., m] using list(range(1, m + 1))
• Initialize an empty result list ans to store positions

Processing Each Query:

For each value v in queries:

1. Find Position: Use p.index(v) to find the current position of value v in the permutation. This returns the 0-based index where v is located.

2. Record Result: Append this position j to our answer list ans.append(j).

3. Move to Front:

   • Remove the element from its current position using p.pop(j)
   • Insert it at the beginning using p.insert(0, v)

Data Structure Choice:

The solution uses a Python list to represent the permutation. While lists have O(n) complexity for index lookup, removal, and insertion operations, the simplicity of implementation makes this approach practical for the problem's constraints.

Step-by-step Example:

If m = 4 and queries = [3, 1]:

• Start: p = [1, 2, 3, 4]
• Query 3: Found at index 2, move to front → p = [3, 1, 2, 4], record 2
• Query 1: Found at index 1, move to front → p = [1, 3, 2, 4], record 1
• Return [2, 1]

The simulation approach directly implements the problem's requirements without any optimization tricks, making it easy to understand and verify while being efficient enough for the given constraints.

Example Walkthrough

Let's walk through a concrete example with m = 5 and queries = [3, 1, 2, 1].

Initial Setup:

• Create permutation: p = [1, 2, 3, 4, 5]
• Result array: ans = []

Processing Query 1: value = 3

• Find position: p.index(3) returns 2 (3 is at index 2)
• Record result: ans = [2]
• Remove 3 from index 2: p.pop(2) → p = [1, 2, 4, 5]
• Insert 3 at front: p.insert(0, 3) → p = [3, 1, 2, 4, 5]

Processing Query 2: value = 1

• Find position: p.index(1) returns 1 (1 is at index 1)
• Record result: ans = [2, 1]
• Remove 1 from index 1: p.pop(1) → p = [3, 2, 4, 5]
• Insert 1 at front: p.insert(0, 1) → p = [1, 3, 2, 4, 5]

Processing Query 3: value = 2

• Find position: p.index(2) returns 2 (2 is at index 2)
• Record result: ans = [2, 1, 2]
• Remove 2 from index 2: p.pop(2) → p = [1, 3, 4, 5]
• Insert 2 at front: p.insert(0, 2) → p = [2, 1, 3, 4, 5]

Processing Query 4: value = 1

• Find position: p.index(1) returns 1 (1 is at index 1)
• Record result: ans = [2, 1, 2, 1]
• Remove 1 from index 1: p.pop(1) → p = [2, 3, 4, 5]
• Insert 1 at front: p.insert(0, 1) → p = [1, 2, 3, 4, 5]

Final Answer: [2, 1, 2, 1]

Notice how elements that were recently queried stay near the front of the permutation, while unqueried elements (like 4 and 5) gradually shift toward the back. This "move-to-front" behavior ensures frequently accessed elements require less searching in subsequent queries.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * m) where n is the length of queries and m is the size of the initial permutation.

• The outer loop iterates through all queries: O(n)
• For each query, we perform:
  • p.index(v): Linear search through the list p, which can have up to m elements: O(m)
  • p.pop(j): Removing an element at index j requires shifting all elements after it: O(m)
  • p.insert(0, v): Inserting at the beginning requires shifting all elements: O(m)
• Total: O(n) * O(m) = O(n * m)

Space Complexity: O(m)

• The list p stores m elements: O(m)
• The answer list ans stores n elements: O(n), but this is considered output space and typically not counted in space complexity analysis
• No additional data structures are used that scale with input size
• Total auxiliary space: O(m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing 1-indexed Values with 0-indexed Positions

A frequent mistake is mixing up the fact that the permutation contains values from 1 to m (1-indexed), while the positions we need to return are 0-indexed.

Incorrect approach:

# Wrong: Trying to use the value directly as an index
position = permutation[query_value]  # This would cause IndexError or wrong result

Correct approach:

# Right: Find the index (position) of the value
position = permutation.index(query_value)

2. Modifying the List While Iterating Without Proper Handling

Some developers might try to optimize by combining operations incorrectly:

Problematic approach:

# Attempting to remove and insert in one line might lead to errors
for query_value in queries:
    result.append(permutation.index(query_value))
    permutation = [query_value] + [x for x in permutation if x != query_value]
    # This creates a new list each time, which is inefficient

Better approach:

# Use pop() and insert() for in-place modifications
current_index = permutation.index(query_value)
result.append(current_index)
permutation.pop(current_index)
permutation.insert(0, query_value)

3. Not Handling the Order of Operations Correctly

The order matters: you must find the index BEFORE moving the element.

Wrong order:

for query_value in queries:
    # Moving first, then finding index - completely wrong!
    permutation.remove(query_value)
    permutation.insert(0, query_value)
    result.append(permutation.index(query_value))  # Always returns 0!

Correct order:

for query_value in queries:
    # Find index first
    current_index = permutation.index(query_value)
    result.append(current_index)
    # Then move the element
    permutation.pop(current_index)
    permutation.insert(0, query_value)

4. Using remove() Instead of pop() Without Considering Performance

While both work functionally, there's a subtle difference:

Less efficient:

current_index = permutation.index(query_value)
result.append(current_index)
permutation.remove(query_value)  # Searches again for the value
permutation.insert(0, query_value)

More efficient:

current_index = permutation.index(query_value)
result.append(current_index)
permutation.pop(current_index)  # Directly removes at known index
permutation.insert(0, query_value)

The pop() approach avoids searching for the element twice since we already know its index.