Queries on a Permutation With Key

Queries on a Permutation With Key

What is this problem about?

The Queries on a Permutation With Key problem starts with the permutation [1,2,...,m] and processes each query: find the position of the query value, record its index, then move the queried element to the front. This coding problem uses a Binary Indexed Tree (Fenwick Tree) to efficiently track positions as elements shift. The array, simulation, and binary indexed tree interview pattern is the core.

Why is this asked in interviews?

Amazon asks this because the naive O(n²) simulation is too slow for large inputs. The efficient solution uses a BIT to answer "how many active elements are before this element" in O(log m) per query. It tests knowledge of BIT for dynamic position tracking.

Algorithmic pattern used

BIT for order statistics + index mapping. Maintain a BIT over m positions. Initially all positions filled. For each query val: find its current physical slot (using binary search or direct mapping). Query BIT for prefix sum up to slot - 1 (= number of elements before it = its 1-indexed position). Record result. Remove from current position in BIT. Insert at front (position 0 logically). Update mapping.

Example explanation

m=5, queries=[3,1,2,1]. Permutation: [1,2,3,4,5].

• Query 3: at index 2 (0-based). Position = 2. Move to front: [3,1,2,4,5].
• Query 1: at index 1. Position = 1. Move to front: [1,3,2,4,5].
• Query 2: at index 2. Position = 2. Move to front: [2,1,3,4,5].
• Query 1: at index 1. Position = 1. Results: [2,1,2,1].

Common mistakes candidates make

• O(n²) simulation (re-scanning array each query).
• Not maintaining a reverse mapping (value → current slot).
• BIT index management errors when elements shift.
• Confusing 0-indexed vs 1-indexed positions.

Interview preparation tip

Queries on a Permutation illustrates dynamic position tracking with a BIT. The key: store elements in "virtual slots" and use BIT prefix sums to compute relative positions. Moving to front = using the next available front slot, reducing from O(n) per query to O(log m). Practice BIT for "count active elements in range" — it's the foundation for many dynamic order statistics problems.