Queries on a Permutation With Key — LeetCode 1409 Python Solution

The 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.

Example

Input

queries = [3,1,2,1], m = 5

Output

[2,1,2,1]

Explanation

The queries are processed as follow:

Python solution

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        p = list(range(1, m + 1))
        ans = []
        for v in queries:
            j = p.index(v)
            ans.append(j)
            p.pop(j)
            p.insert(0, v)
        return ans

Complexity

Related problems