LeetCode 1409 - Queries on a Permutation With Key

LeetCode Problem 1409

Difficulty: 🟡 Medium
Topics: Array, Binary Indexed Tree, Simulation

Solution

Problem Understanding

This problem asks us to simulate a dynamic permutation of integers and answer position queries as elements continuously move.

Initially, we are given a permutation:

P = [1, 2, 3, ..., m]

For every value in the queries array, we must perform two operations:

1. Find the current position of queries[i] in the permutation P, using 0-based indexing.
2. Move that queried value to the front of the permutation.

The position found before moving the element becomes part of the result array.

In other words, every query changes the arrangement of the permutation, and future queries depend on the updated order. This means the permutation evolves over time, so we cannot process each query independently.

For example, if:

P = [1,2,3,4,5]
queries[i] = 3

The value 3 is currently at index 2, so we record 2 in the answer. Then we move 3 to the front:

P = [3,1,2,4,5]

The next query works on this modified permutation.

The input consists of:

• queries, an array of integers representing the requested values
• m, which defines the initial permutation [1,2,3,...,m]

The output is an array where each element represents the position of the corresponding query value before it was moved to the front.

The constraints are relatively small:

• m <= 1000
• queries.length <= m <= 1000

These limits tell us that even a quadratic solution may be acceptable. Since the maximum work is around 1000 × 1000 = 10^6, brute force is feasible. However, the problem is tagged with Binary Indexed Tree, which suggests there is a more scalable and elegant approach.

Several edge cases are important to consider. Repeated queries can move the same number to the front multiple times, which means future accesses may suddenly become index 0. Queries may also repeatedly target values near the end of the permutation, forcing many shifts in a naive implementation. The problem guarantees all query values are valid integers between 1 and m, so we never need to handle missing elements or invalid inputs.

Approaches

Brute Force Simulation

The most straightforward solution is to directly simulate the permutation.

We maintain a list representing the current permutation. For every query:

1. Search for the queried value using a linear scan.
2. Record its index.
3. Remove it from its current position.
4. Insert it at the beginning.

This works because it exactly follows the rules of the problem. Every query updates the permutation correctly, so later queries observe the proper ordering.

However, locating an element takes O(m) time, and removing plus inserting into a list also costs O(m) because elements shift positions. Since we process every query this way, the total complexity becomes O(n × m) where n = len(queries).

Although acceptable under the current constraints, this method becomes inefficient for larger inputs.

Optimal Approach, Binary Indexed Tree + Position Tracking

The key observation is that we repeatedly need to answer this question:

"How many elements appear before a given number?"

This is a classic prefix sum problem.

Instead of physically moving elements in an array, we can assign every number a position index and maintain a structure that tracks which positions are occupied.

We use:

• A hash map / array to store the current position of every number.
• A Binary Indexed Tree (Fenwick Tree) to efficiently count how many elements exist before a position.

The trick is to reserve space at the front for future moves.

Suppose there are n queries.

We initially place numbers at positions:

n+1, n+2, ..., n+m

The first n positions remain empty.

Whenever a queried value appears:

1. Use the Binary Indexed Tree to count how many active elements exist before its position.
2. Remove the number from its old position.
3. Move it to the next free front position.
4. Update its stored position.

This avoids expensive shifting operations entirely.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(m)	Direct simulation of the permutation
Optimal	O((n + m) log(n + m))	O(n + m)	Uses Binary Indexed Tree for efficient position queries

Algorithm Walkthrough

1. Let n = len(queries) and create a Binary Indexed Tree of size n + m.

We allocate extra space because queried elements will move to the front. Instead of shifting values, we assign them new smaller indices. 2. Store the initial position of every value from 1 to m.

Initially, value x is placed at:

position[x] = n + x

We intentionally leave positions [1...n] empty for future front insertions. 3. Mark all initial positions as occupied in the Binary Indexed Tree.

Every active number contributes 1 at its current position. 4. Maintain a variable called front_position.

Start with:

front_position = n

This represents the next available slot at the front. 5. Process each query one at a time.

For the queried value x:

1. Get its current position from position[x].
2. Query the Binary Indexed Tree for the count of elements before it:

rank = prefix_sum(current_position) - 1

We subtract 1 because the prefix sum includes the element itself, but we only want elements before it. 3. Add this rank to the result array. 4. Remove the element from its old position by subtracting 1 in the Binary Indexed Tree. 5. Move it to front_position by adding 1 there. 6. Update position[x]. 7. Decrement front_position. 6. Return the result array after processing all queries.

Why it works

The Binary Indexed Tree always maintains an accurate count of which positions currently contain elements. Since every value has a unique position, the prefix sum up to an element's location equals the number of active elements before or at that position. Subtracting one gives the exact 0-based index of that value in the current permutation. Updating positions after every query preserves the correct ordering invariant, ensuring all future queries observe the updated permutation.

Python Solution

from typing import List

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        n = len(queries)
        size = n + m

        # Fenwick Tree
        fenwick = [0] * (size + 1)

        def update(index: int, delta: int) -> None:
            while index <= size:
                fenwick[index] += delta
                index += index & -index

        def query(index: int) -> int:
            total = 0
            while index > 0:
                total += fenwick[index]
                index -= index & -index
            return total

        # Store current positions of numbers
        positions = [0] * (m + 1)

        # Initialize permutation positions
        for value in range(1, m + 1):
            position = n + value
            positions[value] = position
            update(position, 1)

        result = []
        front_position = n

        for value in queries:
            current_position = positions[value]

            # Find 0-based index
            index = query(current_position) - 1
            result.append(index)

            # Remove old position
            update(current_position, -1)

            # Move to front
            positions[value] = front_position
            update(front_position, 1)

            front_position -= 1

        return result

The implementation starts by creating a Fenwick Tree, which efficiently supports prefix sum operations and point updates in logarithmic time. The update() helper adjusts the count at a specific position, while query() computes how many active elements exist up to a given position.

The positions array stores the current location of each number. Instead of placing elements directly at the front of an array, every value initially starts in the range [n+1, n+m], leaving room for future front insertions.

For every query, the code retrieves the current position of the queried value and computes its rank using a Fenwick prefix sum. Since the queried element contributes to its own prefix sum, subtracting one converts the result into the required 0-based index.

After recording the answer, the implementation removes the element from its old location, inserts it into the current front slot, updates its stored position, and moves the front pointer leftward for the next query.

Go Solution

func processQueries(queries []int, m int) []int {
	n := len(queries)
	size := n + m

	// Fenwick Tree
	fenwick := make([]int, size+1)

	update := func(index int, delta int) {
		for index <= size {
			fenwick[index] += delta
			index += index & -index
		}
	}

	query := func(index int) int {
		sum := 0
		for index > 0 {
			sum += fenwick[index]
			index -= index & -index
		}
		return sum
	}

	// Current positions of each value
	positions := make([]int, m+1)

	// Initialize positions
	for value := 1; value <= m; value++ {
		position := n + value
		positions[value] = position
		update(position, 1)
	}

	result := make([]int, 0, n)
	frontPosition := n

	for _, value := range queries {
		currentPosition := positions[value]

		// Get 0-based index
		index := query(currentPosition) - 1
		result = append(result, index)

		// Remove from old position
		update(currentPosition, -1)

		// Move to front
		positions[value] = frontPosition
		update(frontPosition, 1)

		frontPosition--
	}

	return result
}

The Go implementation follows the same logic as the Python solution. Since Go does not support nested named functions as naturally as Python, the Fenwick Tree helpers are implemented as closures. Slices are used for dynamic storage of both the Fenwick Tree and positions.

No special handling for nil versus empty slices is needed because the problem guarantees valid input sizes. Integer overflow is also not a concern because the constraints are very small and all values comfortably fit within Go's int type.

Worked Examples

Example 1

queries = [3,1,2,1]
m = 5
n = 4

Initial positions:

Value	Position
1	5
2	6
3	7
4	8
5	9

Front position starts at 4.

Query	Current Position	Prefix Sum	Result Index	New Position	Front Position After
3	7	3	2	4	3
1	5	2	1	3	2
2	6	3	2	2	1
1	3	2	1	1	0

Final answer:

[2,1,2,1]

Example 2

queries = [4,1,2,2]
m = 4
n = 4

Initial positions:

Value	Position
1	5
2	6
3	7
4	8

Query	Current Position	Prefix Sum	Result Index	New Position
4	8	4	3	4
1	5	2	1	3
2	6	3	2	2
2	2	1	0	1

Final answer:

[3,1,2,0]

Example 3

queries = [7,5,5,8,3]
m = 8
n = 5

Initial positions:

1→6, 2→7, 3→8, 4→9, 5→10, 6→11, 7→12, 8→13

Query	Current Position	Result Index	New Position
7	12	6	5
5	10	5	4
5	4	0	3
8	13	7	2
3	8	5	1

Final answer:

[6,5,0,7,5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) log(n + m))	Every query performs Fenwick updates and prefix sums
Space	O(n + m)	Extra storage for Fenwick Tree and position mapping

The initialization phase inserts m elements into the Binary Indexed Tree, costing O(m log(n+m)). Each query performs one prefix sum and two updates, each requiring O(log(n+m)) time. Since there are n queries, the total runtime becomes O((n + m) log(n + m)).

The extra memory comes from the Fenwick Tree of size n + m and the position array storing current locations of values 1 through m.

Test Cases

class Solution:
    def processQueries(self, queries, m):
        n = len(queries)
        size = n + m

        fenwick = [0] * (size + 1)

        def update(index, delta):
            while index <= size:
                fenwick[index] += delta
                index += index & -index

        def query(index):
            total = 0
            while index > 0:
                total += fenwick[index]
                index -= index & -index
            return total

        positions = [0] * (m + 1)

        for value in range(1, m + 1):
            position = n + value
            positions[value] = position
            update(position, 1)

        result = []
        front_position = n

        for value in queries:
            current_position = positions[value]

            index = query(current_position) - 1
            result.append(index)

            update(current_position, -1)

            positions[value] = front_position
            update(front_position, 1)

            front_position -= 1

        return result

solution = Solution()

assert solution.processQueries([3, 1, 2, 1], 5) == [2, 1, 2, 1]  # Example 1
assert solution.processQueries([4, 1, 2, 2], 4) == [3, 1, 2, 0]  # Example 2
assert solution.processQueries([7, 5, 5, 8, 3], 8) == [6, 5, 0, 7, 5]  # Example 3

assert solution.processQueries([1], 1) == [0]  # Minimum input size
assert solution.processQueries([1, 1, 1], 3) == [0, 0, 0]  # Same element repeatedly
assert solution.processQueries([3, 3, 3], 3) == [2, 0, 0]  # Element moves to front
assert solution.processQueries([5, 4, 3, 2, 1], 5) == [4, 4, 4, 4, 4]  # Reverse access order
assert solution.processQueries([1, 2, 3, 4, 5], 5) == [0, 1, 2, 3, 4]  # Already front sequence
assert solution.processQueries([2, 1, 2, 1], 2) == [1, 1, 1, 1]  # Small repeated permutation

Test Summary

Test	Why
[3,1,2,1], 5	Verifies Example 1
[4,1,2,2], 4	Verifies Example 2
[7,5,5,8,3], 8	Verifies Example 3
[1], 1	Minimum valid input
[1,1,1], 3	Repeated querying of front element
[3,3,3], 3	Ensures moved element remains at front
[5,4,3,2,1], 5	Stress test for back-to-front movement
[1,2,3,4,5], 5	Sequential access pattern
[2,1,2,1], 2	Small repeated interactions

Edge Cases

Repeated Queries to the Same Value

A common source of bugs is repeatedly querying the same element. After the first query, the element should already be at the front, meaning all later accesses should return index 0.

For example:

queries = [3,3,3]
m = 3

After the first query, 3 moves to the front. The implementation correctly updates its position in the positions array, so subsequent prefix sum calculations return 0.

Minimum Input Size

The smallest valid case is:

queries = [1]
m = 1

Since the permutation is [1], the only value already exists at index 0. The implementation handles this correctly because the Fenwick Tree still supports a single position and the prefix sum logic remains valid.

Values Near the End of the Permutation

Queries may repeatedly target elements near the back of the current permutation, which could be expensive in a naive shifting solution.

For example:

queries = [5,4,3,2,1]
m = 5

A brute force approach repeatedly shifts many elements. The Binary Indexed Tree solution avoids physical movement entirely by updating position mappings and occupancy counts, maintaining logarithmic performance for every query.