Problem

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

  • In the beginning, you have the permutation P=[1,2,3,...,m].
  • For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1] 
Explanation: The queries are processed as follow: 
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is **2** , then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. 
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is **1** , then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. 
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is **2** , then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. 
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is **1** , then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. 
Therefore, the array containing the result is [2,1,2,1].

Example 2

1
2

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]

Example 3

1
2

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]

Constraints

  • 1 <= m <= 10^3
  • 1 <= queries.length <= m
  • 1 <= queries[i] <= m

Solution

Method 1 – Simulation with List

Intuition

We can directly simulate the process by maintaining the permutation as a list. For each query, find the index of the value, record it, and move the value to the front.

Approach

  1. Initialize the permutation P as [1, 2, ..., m].
  2. For each query, find the index of the value in P.
  3. Record the index, remove the value from its position, and insert it at the front.
  4. Repeat for all queries and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> p(m);
        iota(p.begin(), p.end(), 1);
        vector<int> ans;
        for (int q : queries) {
            auto it = find(p.begin(), p.end(), q);
            int idx = it - p.begin();
            ans.push_back(idx);
            p.erase(it);
            p.insert(p.begin(), q);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func processQueries(queries []int, m int) []int {
    p := make([]int, m)
    for i := 0; i < m; i++ { p[i] = i+1 }
    ans := make([]int, len(queries))
    for i, q := range queries {
        idx := 0
        for j, v := range p {
            if v == q { idx = j; break }
        }
        ans[i] = idx
        copy(p[1:idx+1], p[0:idx])
        p[0] = q
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int idx = p.indexOf(queries[i]);
            ans[i] = idx;
            p.remove(idx);
            p.add(0, queries[i]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun processQueries(queries: IntArray, m: Int): IntArray {
        val p = MutableList(m) { it + 1 }
        return queries.map { q ->
            val idx = p.indexOf(q)
            p.removeAt(idx)
            p.add(0, q)
            idx
        }.toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from typing import List
class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        p = list(range(1, m+1))
        ans = []
        for q in queries:
            idx = p.index(q)
            ans.append(idx)
            p.pop(idx)
            p.insert(0, q)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn process_queries(queries: Vec<i32>, m: i32) -> Vec<i32> {
        let mut p: Vec<i32> = (1..=m).collect();
        let mut ans = Vec::with_capacity(queries.len());
        for q in queries {
            let idx = p.iter().position(|&x| x == q).unwrap();
            ans.push(idx as i32);
            p.remove(idx);
            p.insert(0, q);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    processQueries(queries: number[], m: number): number[] {
        const p = Array.from({length: m}, (_, i) => i+1);
        return queries.map(q => {
            const idx = p.indexOf(q);
            p.splice(idx, 1);
            p.unshift(q);
            return idx;
        });
    }
}

Complexity

  • ⏰ Time complexity: O(Q * M), where Q is the number of queries and M is the size of the permutation. Each query may scan up to M elements.
  • 🧺 Space complexity: O(M), for the permutation array.