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:
P=[1,2,3,...,m].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.
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] <= mProblem 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.
This approach utilizes a simple linear scan to locate each query item within the permutation array. Post discovery, this item is repositioned to the start of the array. Specifically, we iterate over the 'queries' array, locate 'queries[i]' within 'P', log the index, then elevate the item to the permutation's forefront by erasing it from its original position and reinserting it at the beginning. Despite its straightforwardness, this methodology can be suboptimal, especially for substantial 'm', given its O(n * m) time complexity.
The C implementation begins by constructing a permutation array 'P' encompassing integers from 1 to m. It proceeds with sequentially scanning for the queried element, calculating its index, and subsequently repositioning this element to the head of the array. This is accomplished by shifting intervening elements to the right. This approach is straightforward but less efficient for larger arrays.
Time complexity: O(n * m), Space complexity: O(m)
This advanced approach employs a Binary Indexed Tree (BIT) for enhanced efficiency, minimizing the time required to reposition each queried element. The idea involves leveraging the BIT to keep track of current positions and perform range sum queries efficiently. This reduces the need for repeated O(n) operations encountered in naive searching strategies.
In this Python solution, a Fenwick Tree (Binary Indexed Tree) is employed to efficiently manage indices and cumulative sums. It allows fast updates and queries on prefix sums, enabling us to calculate the needed offset for answers effectively and manage the permutations without frequent array manipulation.
Python
Time complexity: O((n + m) * log(n + m)), Space complexity: O(n + m)
The problem's data scale is not large, so we can directly simulate it.
The Binary Indexed Tree (BIT), also known as the Fenwick Tree, efficiently supports the following two operations:
update(x, delta): Adds a value delta to the element at position x in the sequence.query(x): Queries the sum of the sequence over the interval [1,...,x], i.e., the prefix sum at position x.Both operations have a time complexity of O(log n).
The fundamental functionality of the Binary Indexed Tree is to count the number of elements smaller than a given element x. This comparison is abstract and can refer to size, coordinate, mass, etc.
For example, given the array a[5] = {2, 5, 3, 4, 1}, the task is to compute b[i] = the number of elements to the left of position i that are less than or equal to a[i]. For this example, b[5] = {0, 1, 1, 2, 0}.
The solution is to traverse the array, first calculating query(a[i]) for each position, and then updating the Binary Indexed Tree with update(a[i], 1). When the range of numbers is large, discretization is necessary, which involves removing duplicates, sorting, and then assigning an index to each number.
| Approach | Complexity |
|---|---|
| Naive Linear Search Approach | Time complexity: O(n * m), Space complexity: O(m) |
| Using Binary Indexed Tree for Efficient Index Management | Time complexity: O((n + m) * log(n + m)), Space complexity: O(n + m) |
| Simulation | — |
| Binary Indexed Tree | — |
| 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 |
花花酱 LeetCode 1409. Queries on a Permutation With Key - 刷题找工作 EP319 • Hua Hua • 1,584 views views
Watch 9 more video solutions →Practice Queries on a Permutation With Key with our built-in code editor and test cases.
Practice on FleetCode