Queries on a Permutation With Key

Med

#1304Time: 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.

Data structures

Array Binary Indexed Tree

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

1. Initialize a LinkedList P with values from 1 to m.
1. Create a result array of the same size as queries.
1. 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.
1. Return the result array.

Walkthrough

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:

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.
This index is the result for the current query, so we store it in our result array.
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:

1import java.util.LinkedList;2 3class Solution {4    public int[] processQueries(int[] queries, int m) {5        LinkedList<Integer> p = new LinkedList<>();6        for (int i = 1; i <= m; i++) {7            p.add(i);8        }9 10        int[] result = new int[queries.length];11        for (int i = 0; i < queries.length; i++) {12            int queryVal = queries[i];13            14            // Find the position (index) of the query value15            int index = p.indexOf(queryVal);16            result[i] = index;17            18            // Move the element to the front19            // Note: p.remove(Integer.valueOf(queryVal)) would also work20            p.remove(index);21            p.addFirst(queryVal);22        }23        24        return result;25    }26}

Complexity

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.

Trade-offs

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.

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.

Algorithm

1. Define a virtual space of size N = m + q.
1. Create a map valToPos to store the position of each number 1..m. Initialize valToPos[i] = q + i.
1. Create a Fenwick Tree (BIT) of size N. Initialize it by adding 1 at each initial position q+1, ..., q+m.
1. Initialize a pointer for the next available front position, nextAvailablePos = q.
1. 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.
1. Return the collected results.

Walkthrough

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:

We look up its current position, pos = valToPos[val].
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.
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).
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)).
We also update valToPos[val] to the new position.

This process is repeated for all queries.

Here is the Java implementation:

1class Solution {2    int[] bit;3    int size;4 5    void update(int index, int val) {6        for (; index <= size; index += index & -index) {7            bit[index] += val;8        }9    }10 11    int query(int index) {12        int sum = 0;13        for (; index > 0; index -= index & -index) {14            sum += bit[index];15        }16        return sum;17    }18 19    public int[] processQueries(int[] queries, int m) {20        int qLen = queries.length;21        this.size = m + qLen;22        this.bit = new int[size + 1];23        24        int[] valToPos = new int[m + 1];25        26        for (int i = 1; i <= m; i++) {27            valToPos[i] = qLen + i;28            update(qLen + i, 1);29        }30        31        int[] result = new int[qLen];32        int nextAvailablePos = qLen;33        34        for (int i = 0; i < qLen; i++) {35            int queryVal = queries[i];36            int currentPos = valToPos[queryVal];37            38            result[i] = query(currentPos - 1);39            40            update(currentPos, -1);41            valToPos[queryVal] = nextAvailablePos;42            update(nextAvailablePos, 1);43            44            nextAvailablePos--;45        }46        47        return result;48    }49}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] processQueries(int[] queries, int m) {4    List<Integer> p = new LinkedList<>();5    for (int i = 1; i <= m; ++i) {6      p.add(i);7    }8    int[] ans = new int[queries.length];9    int i = 0;10    for (int v : queries) {11      int j = p.indexOf(v);12      ans[i++] = j;13      p.remove(j);14      p.add(0, v);15    }16    return ans;17  }18}

1class Solution {2public:3  vector<int> processQueries(vector<int> &queries, int m) {4    vector<int> p(m);5    iota(p.begin(), p.end(), 1);6    vector<int> ans;7    for (int v : queries) {8      int j = 0;9      for (int i = 0; i < m; ++i) {10        if (p[i] == v) {11          j = i;12          break;13        }14      }15      ans.push_back(j);16      p.erase(p.begin() + j);17      p.insert(p.begin(), v);18    }19    return ans;20  }21};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem