Queries on a Permutation With Key - Video Solutions

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.