MediumNo. 1409

Queries on a Permutation With Key — LeetCode 1409 Python Solution

Topics
Binary Indexed Tree, Array, Simulation
Reading time
2 min

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

PythonSolution
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

Time
O(n)
Space · auxiliary
O(1) to O(n)

Related problems

Frequently asked questions

How hard is LeetCode 1409. Queries on a Permutation With Key?

LeetCode 1409. Queries on a Permutation With Key is rated Medium on LeetCode.

What topics does LeetCode 1409. Queries on a Permutation With Key cover?

LeetCode 1409. Queries on a Permutation With Key is tagged Binary Indexed Tree, Array and Simulation on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.