Domain 2MediumMEDIUM

Queries on a Permutation With Key

Simulate the permutation updates using a list, finding indices and moving elements to the front. Given constraints (m <= 10^3), O(N*m) complexity is acceptable.

Domain: medium•Updated: 2026-09-16
#Simulation#Array#O(Q*M)#O(M)

Problem Breakdown

We are given an initial permutation P=[1,2,…,m]P = [1, 2, \dots, m] and a list of queries queries. For each query value in the list, we must:

  1. Find its current index (0-based) within the dynamic array PP. This index is our result for that step.
  2. Move this element to position 0 (the beginning) of PP, shifting all other elements at indices greater than or equal to it one spot to the right.

Inputs: queries (list of integers), m (integer).
Outputs: A list containing the index found for each query step.
Constraints:

  • 1≤m≤1031 \le m \le 10^3
  • Length of queries ≤m\le m
  • Values in queries are between 1 and mm.

The core challenge is maintaining the state of permutation PP efficiently as it changes after every operation, while correctly identifying indices. Since elements move to the front frequently, their relative order among themselves (excluding those moved) remains consistent until one of them moves again. The tricky part is that moving an element affects the index of all subsequent elements in the array.

Intuition

Let’s start with a brute force approach:

  1. Initialize PP as [1, 2, ..., m].
  2. For each query value q:
    • Scan PP to find where q is located (let this be index idx).
    • Record idx.
    • Remove q from its current position and insert it at the beginning of PP.

Complexity Analysis:

  • Finding an element in a list takes O(m)O(m) time.
  • Removing/inserting into a Python list (which is implemented as a dynamic array) involves shifting elements, which also takes proportional to the number of elements shifted (O(m)O(m)).
  • If we have n queries and each operation takes O(m)O(m), the total complexity is O(n⋅m)O(n \cdot m).

Given the constraints where both mm and query length are up to 10310^3, the maximum operations would be roughly 10610^6. In modern interview settings (and LeetCode specifically for this problem ID), a time limit of ~2 seconds allows for approximately 10810^8 simple operations. Therefore, an O(n⋅m)O(n \cdot m) simulation is well within acceptable limits and avoids over-engineering with complex data structures like Fenwick Trees or Segment Trees unless constraints were significantly larger (e.g., m>105m > 10^5).

Approach

We will implement the direct simulation approach because it balances readability, correctness, and performance for these specific constraints.

  1. Initialize a list P containing numbers from 1 to m.
  2. Iterate through each number in queries:
    • Use Python’s built-in .index() method (or manual loop) to find the current position of the query value in PP. This gives us our result for this step.
    • Store this index in a results list.
    • Remove the element from its found position using .pop(index) and insert it at the front using .insert(0, val). Note that Python’s internal implementation handles these shifts efficiently (memmove).

Complexity Analysis

  • Time Complexity: O(Q⋅M)O(Q \cdot M) where QQ is len(queries) and MM is m. Each query involves a linear scan to find the element (O(M)O(M)) plus shifting elements during insertion/deletion (O(M)O(M)). With given constraints, this results in ≈106\approx 10^6 operations.
  • Space Complexity: O(M)O(M) for storing the permutation array and result list (excluding input storage).

Solution

from typing import List

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        # Initialize permutation P with values 1 to m.
        p = list(range(1, m + 1))
        
        results = []
        
        for q in queries:
            # Find current index of query value 'q' (0-based). 
            idx = p.index(q)
            
            # Record the result immediately.
            results.append(idx)
            
            # Move element to front by removing from found position and inserting at 0.
            val_at_idx = p.pop(idx)
            p.insert(0, val_at_idx)
            
        return results

```python
class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        # Initialize permutation P with values 1 to m.
        p = list(range(1, m + 1))