# Queries on a Permutation With Key
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/queries-on-a-permutation-with-key)
Canonical: https://scaleengineer.com/dsa/problems/queries-on-a-permutation-with-key
**Data structures:** Array, Binary Indexed Tree
---
## Problem
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`

# Approaches
## Brute Force Simulation using a List
This approach directly simulates the process described in the problem. We use a list data structure, such as `java.util.LinkedList`, to represent the permutation `P`. For each query, we find the element, record its index, and then move it to the front of the list.
**Time:** O(q * m), where `q` is the number of queries and `m` is the maximum value. For each of the `q` queries, we perform `indexOf` and `remove(index)`, both of which can take up to O(m) time in the worst case as they may require traversing a portion of the list. · **Space:** O(m + q) or simply O(m) since `q <= m`. We need O(m) space for the permutation `P` and O(q) space for the result array.
**Pros:** Very simple and intuitive to implement.; Directly follows the problem description.
**Cons:** The time complexity of O(q * m) can be slow if `m` and `q` are large, although it passes within the given constraints.
### Explanation
We start by initializing a `LinkedList` named `P` with integers from 1 to `m`. A `LinkedList` is chosen because it offers an efficient `addFirst` operation (O(1)), which is ideal for moving an element to the beginning.

We also initialize a result array to store the answers to the queries.

We then iterate through each `query` in the `queries` array. For each `query`:
1.  We find the 0-based index of the `query` value in `P`. The `indexOf` method of the list is used for this, which performs a linear scan.
2.  This index is the result for the current query, so we store it in our result array.
3.  We then move the element to the front. This is a two-step process: first, we remove the element from its current position, and second, we add it to the beginning of the list.

After processing all queries, we return the result array.

Here is the Java implementation:
```java
import java.util.LinkedList;

class Solution {
    public int[] processQueries(int[] queries, int m) {
        LinkedList<Integer> p = new LinkedList<>();
        for (int i = 1; i <= m; i++) {
            p.add(i);
        }

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int queryVal = queries[i];
            
            // Find the position (index) of the query value
            int index = p.indexOf(queryVal);
            result[i] = index;
            
            // Move the element to the front
            // Note: p.remove(Integer.valueOf(queryVal)) would also work
            p.remove(index);
            p.addFirst(queryVal);
        }
        
        return result;
    }
}
```
### Algorithm
- 1. Initialize a `LinkedList` `P` with values from `1` to `m`.
- 2. Create a `result` array of the same size as `queries`.
- 3. For each `query` in `queries`:
    - a. Find the index of `query` in `P` using a linear search.
    - b. Store this index in the `result` array.
    - c. Remove the `query` element from `P`.
    - d. Add the `query` element to the front of `P`.
- 4. Return the `result` array.

## Optimized Approach using Fenwick Tree (BIT)
This approach improves the time complexity by using a more advanced data structure, a Fenwick Tree (also known as a Binary Indexed Tree or BIT). Instead of physically moving elements in a list, we use a clever mapping scheme. We map each number to a position in a larger, virtual array and use the BIT to efficiently count how many numbers are currently positioned before it.
**Time:** O((m+q) * log(m+q)). The initialization involves `m` updates to the BIT, taking O(m * log(m+q)). Each of the `q` queries involves one query and two updates on the BIT, taking O(log(m+q)) time per query. The total is O(m*log(m+q) + q*log(m+q)). · **Space:** O(m+q). We need O(m) for `valToPos`, O(m+q) for the BIT, and O(q) for the result. The dominant term is O(m+q).
**Pros:** Significantly more efficient than the brute-force approach, especially for larger `m` and `q`.; Demonstrates the application of advanced data structures to solve problems that seem to require linear scans.
**Cons:** More complex to understand and implement.; Requires knowledge of Fenwick Trees.; Uses more space than the brute-force approach.
### Explanation
The core idea is to avoid the O(m) cost of finding an element's index and moving it. A BIT allows us to perform two key operations in O(log N) time: updating a value at an index and querying the sum of a prefix.

We set up a virtual space of `m + q` positions, where `q` is the number of queries. Initially, the numbers `1, 2, ..., m` are placed at positions `q+1, q+2, ..., q+m`. The first `q` positions (`1, ..., q`) are left empty to be used for elements that are moved to the front.

We use an array, `valToPos`, to keep track of the current position of each number. `valToPos[i]` stores the position of number `i`.

The BIT, of size `m+q`, will store a `1` at an occupied position and `0` otherwise. A query `BIT.query(k)` will thus give us the count of occupied positions up to `k`.

For each query `val`:
1.  We look up its current position, `pos = valToPos[val]`.
2.  The number of elements before it is the number of occupied slots in the range `[1, pos-1]`. This is exactly what `BIT.query(pos - 1)` calculates. This value is our result for the query.
3.  We then simulate the "move to front" operation. We pick a new position from the reserved front space (e.g., starting from `q` and going down).
4.  We update the BIT by setting the old position `pos` to `0` (via `update(pos, -1)`) and the new front position to `1` (via `update(new_pos, 1)`).
5.  We also update `valToPos[val]` to the new position.

This process is repeated for all queries.

Here is the Java implementation:
```java
class Solution {
    int[] bit;
    int size;

    void update(int index, int val) {
        for (; index <= size; index += index & -index) {
            bit[index] += val;
        }
    }

    int query(int index) {
        int sum = 0;
        for (; index > 0; index -= index & -index) {
            sum += bit[index];
        }
        return sum;
    }

    public int[] processQueries(int[] queries, int m) {
        int qLen = queries.length;
        this.size = m + qLen;
        this.bit = new int[size + 1];
        
        int[] valToPos = new int[m + 1];
        
        for (int i = 1; i <= m; i++) {
            valToPos[i] = qLen + i;
            update(qLen + i, 1);
        }
        
        int[] result = new int[qLen];
        int nextAvailablePos = qLen;
        
        for (int i = 0; i < qLen; i++) {
            int queryVal = queries[i];
            int currentPos = valToPos[queryVal];
            
            result[i] = query(currentPos - 1);
            
            update(currentPos, -1);
            valToPos[queryVal] = nextAvailablePos;
            update(nextAvailablePos, 1);
            
            nextAvailablePos--;
        }
        
        return result;
    }
}
```
### Algorithm
- 1. Define a virtual space of size `N = m + q`.
- 2. Create a map `valToPos` to store the position of each number `1..m`. Initialize `valToPos[i] = q + i`.
- 3. Create a Fenwick Tree (BIT) of size `N`. Initialize it by adding `1` at each initial position `q+1, ..., q+m`.
- 4. Initialize a pointer for the next available front position, `nextAvailablePos = q`.
- 5. For each `queryVal` in `queries`:
    - a. Get its current position: `pos = valToPos[queryVal]`.
    - b. Find the number of elements before it by querying the BIT: `result = BIT.query(pos - 1)`.
    - c. Update the structures to reflect the move:
        - i. Mark the old position as empty: `BIT.update(pos, -1)`.
        - ii. Update the map: `valToPos[queryVal] = nextAvailablePos`.
        - iii. Mark the new position as occupied: `BIT.update(nextAvailablePos, 1)`.
        - iv. Decrement `nextAvailablePos`.
- 6. Return the collected results.

# Solutions
### Java

```java
class Solution {
public
  int[] processQueries(int[] queries, int m) {
    List<Integer> p = new LinkedList<>();
    for (int i = 1; i <= m; ++i) {
      p.add(i);
    }
    int[] ans = new int[queries.length];
    int i = 0;
    for (int v : queries) {
      int j = p.indexOf(v);
      ans[i++] = j;
      p.remove(j);
      p.add(0, v);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> processQueries(vector<int> &queries, int m) {
    vector<int> p(m);
    iota(p.begin(), p.end(), 1);
    vector<int> ans;
    for (int v : queries) {
      int j = 0;
      for (int i = 0; i < m; ++i) {
        if (p[i] == v) {
          j = i;
          break;
        }
      }
      ans.push_back(j);
      p.erase(p.begin() + j);
      p.insert(p.begin(), v);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]: p = list(range(1, m + 1)) ans = [] for v in queries: j = p . index(v) ans . append(j) p . pop(j) p . insert(0, v) return ans

```