Queries on a Permutation With Key - Video Solutions
花花酱 LeetCode 1409. Queries on a Permutation With Key - 刷题找工作 EP319
Queries on a Permutation With Key - Video Solution
Watch 10 video solutions for Queries on a Permutation With Key, a medium level problem involving Array, Binary Indexed Tree, Simulation. This walkthrough by Hua Hua has 1,586 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 ofqueries[i]in the permutationP(indexing from 0) and then move this at the beginning of the permutationP. Notice that the position ofqueries[i]inPis the result forqueries[i].
Return an array containing the result for the given queries.
Example 1:
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:
Input: queries = [4,1,2,2], m = 4 Output: [3,1,2,0]
Example 3:
Input: queries = [7,5,5,8,3], m = 8 Output: [6,5,0,7,5]
Constraints:
1 <= m <= 10^31 <= queries.length <= m1 <= queries[i] <= m
Approach Overview
Problem Overview: You start with a permutation P = [1, 2, ..., m]. For each value in the queries array, find its current index in the permutation, record that index, then move the value to the front of the permutation. The permutation keeps changing after every query.
Approach 1: Naive Linear Search Simulation (Time: O(m * q), Space: O(m))
The direct approach simulates the permutation operations exactly as described. Store the permutation in an array and for each query perform a linear scan to find the position of the queried value. After locating it, append the index to the result and move that element to the front by shifting the elements before it one position to the right. This approach relies purely on array manipulation and works well when m and q are small. It clearly models the process but becomes inefficient because each lookup costs O(m) and you repeat it for every query.
This solution mainly uses simple array operations and basic simulation. Despite the higher time complexity, it is often the fastest way to implement the idea during interviews before optimizing.
Approach 2: Binary Indexed Tree for Efficient Index Management (Time: O(q log(m + q)), Space: O(m + q))
The expensive step in the naive solution is repeatedly finding the index of a number after elements shift. A better strategy stores element positions and uses a Binary Indexed Tree (Fenwick Tree) to maintain how many elements exist before a position. Initially place all numbers in positions offset by q so the front area is empty for future moves.
For each query, look up the stored position of the value and use the tree to compute how many active elements appear before it. That count is exactly the index in the permutation. After recording the result, update the tree to remove the element from its old position and reinsert it at the next available front position. Each update and prefix sum takes O(log n), which keeps the whole process efficient even for large inputs.
This approach relies on a Binary Indexed Tree to maintain dynamic prefix counts while elements move. The key insight is separating logical order (computed with prefix sums) from physical storage of elements.
Recommended for interviews: Start with the simulation approach to demonstrate understanding of the permutation updates. Then optimize using a Binary Indexed Tree. Interviewers typically expect the Fenwick Tree solution because it reduces repeated index searches and handles dynamic position updates efficiently.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Linear Search Simulation | O(m * q) | O(m) | Small constraints or when quickly prototyping the logic of the permutation operations |
| Binary Indexed Tree (Fenwick Tree) | O(q log(m + q)) | O(m + q) | Large inputs where repeated index lookups must be optimized |