Code Implementation

class Solution:
    def processQueries(self, queries, m):
        P = list(range(1, m+1))
        res = []
        for q in queries:
            idx = P.index(q)
            res.append(idx)
            P.pop(idx)
            P.insert(0, q)
        return res
      

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> P(m);
        iota(P.begin(), P.end(), 1);
        vector<int> res;
        for (int q : queries) {
            auto it = find(P.begin(), P.end(), q);
            int idx = it - P.begin();
            res.push_back(idx);
            P.erase(it);
            P.insert(P.begin(), q);
        }
        return res;
    }
};
      

class Solution {
    public int[] processQueries(int[] queries, int m) {
        List<Integer> P = new ArrayList<>();
        for (int i = 1; i <= m; i++) P.add(i);
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int idx = P.indexOf(queries[i]);
            res[i] = idx;
            P.remove(idx);
            P.add(0, queries[i]);
        }
        return res;
    }
}
      

var processQueries = function(queries, m) {
    let P = [];
    for (let i = 1; i <= m; i++) P.push(i);
    let res = [];
    for (let q of queries) {
        let idx = P.indexOf(q);
        res.push(idx);
        P.splice(idx, 1);
        P.unshift(q);
    }
    return res;
};
      

Problem Description

You are given an array of integers queries and an integer m. You must process each element in queries as follows:

• Start with a permutation P of the integers from 1 to m (i.e., P = [1, 2, ..., m]).
• For each query q in queries:
  • Find the index of q in P (0-based).
  • Append this index to the result array.
  • Move q to the front of P (so the order of other elements is preserved).

Return the resulting array of indices. Each query is processed in order, and the permutation is updated after each query.

Constraints:

• 1 ≤ m ≤ 10³
• 1 ≤ queries.length ≤ 10⁴
• 1 ≤ queries[i] ≤ m

Thought Process

The core of this problem is simulating a dynamic array where, for each query, you locate an element, record its position, and then move it to the front.

The most straightforward approach is to use a list to represent the permutation and for each query:

• Find the index of the queried element (linear search).
• Remove it and insert it at the front.

To optimize, you might consider data structures that allow faster lookups and moves, such as a linked list or a segment tree with position tracking. However, given the constraints (with m up to 1000), the naive approach is actually fast enough.

The key realization is that the problem is about simulating the process accurately, not about finding a mathematically optimal answer.

Solution Approach

Let's break down the steps to solve the problem:

1. Initialize the permutation:
   • Create an array P containing numbers from 1 to m.
2. Process each query:
   • For each q in queries:
   • Find the index of q in P (using indexOf or equivalent).
   • Add this index to the result array.
   • Remove q from its current position.
   • Insert q at the front (index 0) of P.
3. Return the result:
   • After processing all queries, return the array of indices collected.

Each step is justified because:

• We need to preserve the order of P and update it after every query.
• Direct list operations are simple and efficient enough for the given constraints.

Example Walkthrough

Let's consider queries = [3,1,2,1] and m = 5.

• Start with P = [1,2,3,4,5]
• Process 3:
  • Index is 2 (P[2] = 3)
  • Result: [2]
  • Move 3 to front: P = [3,1,2,4,5]
• Process 1:
  • Index is 1 (P[1] = 1)
  • Result: [2, 1]
  • Move 1 to front: P = [1,3,2,4,5]
• Process 2:
  • Index is 2 (P[2] = 2)
  • Result: [2, 1, 2]
  • Move 2 to front: P = [2,1,3,4,5]
• Process 1:
  • Index is 1 (P[1] = 1)
  • Result: [2, 1, 2, 1]
  • Move 1 to front: P = [1,2,3,4,5]

The final result is [2, 1, 2, 1].

Time and Space Complexity

Brute-force approach:

• For each query, finding the index is O(m), removing and inserting are O(m).
• With n queries, total time is O(n * m).
• Space complexity is O(m) for the permutation array.

Optimized approaches:

• With advanced data structures (e.g., Binary Indexed Tree), you can improve time per query to O(log m), but for the given constraints, this is unnecessary.
• For m up to 1000 and n up to 10,000, the brute-force approach is efficient enough.

Summary

This problem is a simulation of a dynamic array where queried elements are moved to the front after each operation. While there are more advanced ways to optimize for larger m, the constraints allow a direct and intuitive approach using simple list operations. The key insight is that maintaining and updating the permutation after each query is straightforward and efficient for the input sizes given.