1409. Queries on a Permutation With Key

MediumBinary Indexed TreeArraySimulation

Leetcode Link

Problem Description

In this problem, we are given two pieces of information:

An array of queries containing positive integers between 1 and m.
We initially have a permutation P consisting of all integers from 1 to m in ascending order.

The objective is to process each query by following these steps:

Identify the position of the current query element (let's call it queries[i]) in the permutation P. This position is to be considered using 0-based indexing.
Record the position of queries[i] as this is our result for the current query.
Move the element queries[i] from its current position to the beginning of the permutation P.

We are asked to return an array that contains the result for each queries[i] after processing all the queries.

Intuition

To solve this problem, our approach focuses on simulating the process as described in the problem statement. Here is the thinking process for arriving at the solution:

Initial Setup: We start by generating the initial permutation P which is simply a list of integers from 1 to m.
Processing Queries: For each value v in queries, we need to perform the following operations:
- Find Position: Locate the index j of v within list P which represents the initial position of v in the permutation.
- Record Result: The index j is the answer for this query, so it needs to be added to an answer array ans.
- Update Permutation: We then remove v from its current position in P and insert it at the beginning of P.
Maintain Permutation State: Each iteration modifies the permutation P according to the specified rules. Hence, the state of P is always maintained after processing each query.

The code provided implements this intuitive process using a loop to iterate through each query and updating the permutation P by utilizing Python's list methods index(), pop(), and insert(). Eventually, after processing all queries, the result is the ans list containing the positions of each query value before it was moved to the front of the list.

Solution Approach

The implementation of the solution can be walked through as follows using Python's list data structure and some of its built-in methods:

List Creation: We begin by creating the list P that represents the permutation. This is done using range(1, m + 1) which generates an iterable from 1 to m inclusive. The list function is then called to convert this iterable into a list.
```
p = list(range(1, m + 1))
```
Iterating Through Queries: We iterate through each element v in the list of queries with a for loop.
```
for v in queries:
```
Finding Query Position: The index() method of lists is used to find the position j of the value v within the permutation P. As the list is 0-indexed, this will give us the index starting from 0.
```
j = p.index(v)
```
Recording the Position: We append the found position j to our list ans which will eventually be returned as our result array.
```
ans.append(j)
```
Updating the Permutation: To move the query value to the beginning of P, we first remove v from its current position using pop(j) where j is the index found earlier.
```
p.pop(j)
```
Then, we insert the value v at the beginning of P by using the insert() function with 0 as the index to insert at.
```
p.insert(0, v)
```
Returning the Result: After the loop has finished processing all the elements in queries, our answer list ans is returned. This list contains the original positions of each query value before we moved them.

This solution is efficient because accessing an element's index, removing an element, and inserting an element at the beginning of a list all have a time complexity of O(n), making the overall complexity of the algorithm O(n * q) where n is the number of elements in the permutation and q is the number of queries, since each query is processed independently.

The space complexity of the solution is O(m) where m is the size of the permutation, since it’s the space required to store the permutation.

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

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say we're given the following inputs:

queries: [3, 1, 2, 1]
m: 5

The initial permutation P from 1 to m (5 in this case) is [1, 2, 3, 4, 5].

Now we process each query one by one:

The first query is 3.
- We find the position of 3 in P, which is 2.
- We record this position.
- We move 3 to the front of P resulting in the new permutation [3, 1, 2, 4, 5].
The next query is 1.
- Position of 1 is now 1 (it moved because of the previous query).
- We record this position.
- 1 moves to the front, resulting in [1, 3, 2, 4, 5].
The third query is 2.
- Position of 2 is 2.
- We record the position.
- 2 moves to the front, permutation is [2, 1, 3, 4, 5].
The last query is 1.
- Position of 1 is 1 because it was moved to the front earlier.
- We record the position.
- 1 is already at the front, so the permutation remains [2, 1, 3, 4, 5].

Each position we recorded forms our result: [2, 1, 2, 1].

Thus, the final answer after processing all queries is the list of recorded positions [2, 1, 2, 1].

Solution Implementation

1class Solution:
2    def processQueries(self, queries: List[int], m: int) -> List[int]:
3        # Initialize the P sequence with integers from 1 to m
4        p_sequence = list(range(1, m + 1))
5        # Initialize the answer list to store the results
6        results = []
7        # Process each query from the queries list
8        for value in queries:
9            # Find the index of the current value in the P sequence
10            index = p_sequence.index(value)
11            # Append the index to the results list
12            results.append(index)
13            # Remove the current value from its index in P
14            p_sequence.pop(index)
15            # Insert the current value at the beginning of the P sequence
16            p_sequence.insert(0, value)
17        # Return the results list containing the indices
18        return results
19
20# The code assumes the existence of `List` type hint imported from `typing` module
21# If not present in the original code file, it should be added at the top as:
22# from typing import List
23

1class Solution {
2  
3    // Function to process the queries and return the indices of each query in the permutation
4    public int[] processQueries(int[] queries, int m) {
5        // Initialize P as a LinkedList to easily support element removal and insertion at the front
6        List<Integer> permutation = new LinkedList<>();
7      
8        // Fill permutation with elements 1 to m
9        for (int num = 1; num <= m; num++) {
10            permutation.add(num);
11        }
12      
13        // Array to store the answer (indices of each queried element)
14        int[] indices = new int[queries.length];
15      
16        // Initialize index for placing answers
17        int ansIndex = 0;
18      
19        // Process each query in the array
20        for (int query : queries) {
21            // Find the index of the queried number in the permutation
22            int queryIndex = permutation.indexOf(query);
23          
24            // Store the index in the result answer array
25            indices[ansIndex++] = queryIndex;
26          
27            // Remove the queried number from its current position
28            permutation.remove(queryIndex);
29          
30            // Add the queried number to the front of the permutation
31            permutation.add(0, query);
32        }
33      
34        // Return the final array of indices representing the answer
35        return indices;
36    }
37}
38

1#include <vector>
2#include <numeric> // For std::iota
3
4class Solution {
5public:
6    // This function processes the queries on the permutation array and returns the result.
7    vector<int> processQueries(vector<int>& queries, int m) {
8        // Initialize the permutation array 'P' with elements from 1 to 'm'.
9        vector<int> permutation(m);
10        std::iota(permutation.begin(), permutation.end(), 1);
11      
12        // Initialize the answer vector to store the results of the queries.
13        vector<int> answer;
14      
15        // Loop over each value in the queries.
16        for (int value : queries) {
17            // Initialize an index 'foundIndex' to store the position of the value in 'permutation'.
18            int foundIndex = 0;
19          
20            // Search for the value in the permutation array.
21            for (int i = 0; i < m; ++i) {
22                if (permutation[i] == value) {
23                    foundIndex = i; // Store index where value is found.
24                    break; // Exit the loop since we found the value.
25                }
26            }
27          
28            // Add the found index to the answer vector.
29            answer.push_back(foundIndex);
30          
31            // Erase the value from its current position.
32            permutation.erase(permutation.begin() + foundIndex);
33          
34            // Insert the value at the beginning of the permutation array.
35            permutation.insert(permutation.begin(), value);
36        }
37      
38        // Return the results of the queries.
39        return answer;
40    }
41};
42

1function processQueries(queries: number[], m: number): number[] {
2    // Initialize the permutation array 'permutation' with elements from 1 to 'm'.
3    let permutation: number[] = Array.from({ length: m }, (_, index) => index + 1);
4  
5    // Initialize the answer array to store the results of the queries.
6    let answer: number[] = [];
7  
8    // Loop over each value in the queries array.
9    queries.forEach(value => {
10        // Find the index of the 'value' in 'permutation'.
11        let foundIndex = permutation.indexOf(value);
12      
13        // Add the found index to the 'answer' array.
14        answer.push(foundIndex);
15      
16        // Remove the value from its current position.
17        permutation.splice(foundIndex, 1);
18      
19        // Insert the value at the beginning of the permutation array.
20        permutation.unshift(value);
21    });
22  
23    // Return the results of the queries.
24    return answer;
25}
26

Time and Space Complexity

Time Complexity

The time complexity of the provided code primarily depends on two factors:

The cost of searching for an index of a value in the list p which is done in O(m) time where m is the length of p.
The cost of popping and inserting elements to/from the list which can take up to O(m) time.

Since for every value in queries we perform both indexing and pop-insert operations, we multiply this cost by the number of queries n. Therefore, the time complexity is O(n*m), where n is the length of queries.

Space Complexity

The space complexity of the algorithm is to consider the additional space used by the algorithm excluding the input and output.

Here, aside from the space used by the input queries and the output list ans, the code maintains a list p of size m, but since this does not grow with the size of the input queries, the additional space remains constant. Thus, the space complexity is O(1), which means it is constant space complexity as it doesn't depend on the size of the input queries.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know