Skip to main content
Talentd

Queries on a Permutation With Key - Solution & Explanation

MediumArrayBinary Indexed TreeSimulation17 min readAsked at: Amazon
Practice this problem

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 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^3
  • 1 <= queries.length <= m
  • 1 <= 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.

Approach 1: Naive Linear Search Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n * m), Space complexity: O(m)

Try this approach in the editor β†’

Approach 2: Using Binary Indexed Tree for Efficient Index Management

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.

Code

Python

Python

Complexity

Time complexity: O((n + m) * log(n + m)), Space complexity: O(n + m)

Try this approach in the editor β†’

Approach 3: Simulation

The problem's data scale is not large, so we can directly simulate it.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor β†’

Approach 4: Binary Indexed Tree

The Binary Indexed Tree (BIT), also known as the Fenwick Tree, efficiently supports the following two operations:

  1. Point Update update(x, delta): Adds a value delta to the element at position x in the sequence.
  2. Prefix Sum Query 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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
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β€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Linear Search SimulationO(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

Video Solution

θŠ±θŠ±ι…± LeetCode 1409. Queries on a Permutation With Key - εˆ·ι’˜ζ‰Ύε·₯作 EP319 β€’ Hua Hua β€’ 1,586 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Queries on a Permutation With Key easy or hard?
LeetCode classifies this problem as Medium. The simulation idea is straightforward, but recognizing that repeated index lookups can be optimized with a Binary Indexed Tree requires familiarity with advanced data structures.
Queries on a Permutation With Key Python/Java solution
The problem can be implemented in Python, Java, C++, JavaScript, and other languages. The naive version uses an array with linear search and element shifting, while the optimized Python solution often uses a Fenwick Tree to compute indices and update positions efficiently.
How to solve Queries on a Permutation With Key in O(n)?
A strict O(n) solution is not typical because elements continuously change positions. The closest efficient approach uses a Binary Indexed Tree or Fenwick Tree where each query performs prefix sum and update operations in O(log n), giving an overall complexity of O(q log(m + q)).
What is the best approach for Queries on a Permutation With Key?
The most efficient approach uses a Binary Indexed Tree (Fenwick Tree) to track active positions and compute prefix counts. Each query calculates the current index using a prefix sum and then updates the element's position to the front. This reduces repeated searches and achieves O(q log(m + q)) time complexity.
Is Queries on a Permutation With Key asked at Google/Amazon/Meta?
Permutation manipulation and Fenwick Tree problems appear frequently in interviews at companies like Google, Amazon, and Meta. This problem specifically tests simulation skills and knowledge of data structures that support dynamic prefix queries.
What data structure is used in Queries on a Permutation With Key?
The optimal solution uses a Binary Indexed Tree (Fenwick Tree) to maintain prefix counts of active elements. A simple array is sufficient for the brute-force simulation approach, but the Fenwick Tree enables efficient index queries and updates.
What is the time complexity of Queries on a Permutation With Key?
The naive simulation approach runs in O(m * q) time because each query requires a linear search in the permutation. The optimized Binary Indexed Tree approach improves this to O(q log(m + q)) by performing prefix sum and update operations in logarithmic time.

Ready to solve this problem?

Practice Queries on a Permutation With Key with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays