MediumNo. 1409
Queries on a Permutation With Key — LeetCode 1409 Python Solution
- Topics
- Binary Indexed Tree, Array, Simulation
- Reading time
- 2 min
- Source
- leetcode.com
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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(1) to O(n)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0495 | Teemo Attacking | Easy |
| 0985 | Sum of Even Numbers After Queries | Medium |
| 1389 | Create Target Array in the Given Order | Easy |
| 1503 | Last Moment Before All Ants Fall Out of a Plank | Medium |
| 1535 | Find the Winner of an Array Game | Medium |
| 1560 | Most Visited Sector in a Circular Track | Easy |
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.