Queries on a Permutation With Key

Medium

Asked by:

17 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `m`, and what is the maximum size of the queries array?
Are the query values guaranteed to be within the range of 1 to `m` inclusive?
If a query value appears multiple times, how should I handle those subsequent queries?
What should I return if the input array is null or empty?
Can I modify the input permutation array, or should I create a copy?

Brute Force Solution

Approach

We are given a list of instructions and a list of numbers. For each instruction, we must find where that number is in our list, move it to the front, and remember where it used to be. A brute force method will follow the instructions one by one, doing exactly what they say in the most straightforward way.

Here's how the algorithm would work step-by-step:

Start with the first instruction in the list.
Look at the first number. Go through the entire list of numbers, checking each one to see if it's the number the instruction is asking about.
When you find the number in the list, remember its position.
Now, take that number out of the list.
Put that number at the very beginning of the list.
Record the original position of the number as the answer for that instruction.
Move on to the next instruction and repeat the process until you've followed all the instructions.

Code Implementation

def queries_on_permutation_with_key_brute_force(queries, maximum_number):
    permutation = list(range(1, maximum_number + 1))
    result = []

    for query in queries:
        # Find the index of the current query in the permutation
        for index in range(len(permutation)):
            if permutation[index] == query:
                original_position = index
                break

        # Store the original position for the result
        result.append(original_position)

        # Remove the number from its current position
        number = permutation.pop(original_position)

        # Insert number at the front of the permutation
        permutation.insert(0, number)

    return result

Big(O) Analysis

Time Complexity

O(m*n) – The outer loop iterates through m queries. For each query, the inner loop searches for the element within the permutation of size n. In the worst case, we iterate through almost the entire permutation to find the element. Therefore, we have a nested loop structure where the outer loop runs m times and the inner loop runs up to n times. This results in a time complexity of O(m*n).

Space Complexity

O(N) – The provided plain English explanation describes manipulating a list of numbers. Specifically, the list needs to be modified by removing an element and inserting it at the beginning. While the removal and insertion *could* be done in place on some data structures, the explanation implicitly indicates that this list needs to be copied or that an auxiliary list of size N is created to perform these operations efficiently. Therefore, an auxiliary list of size N, where N is the number of numbers in the original list, is needed. The space complexity is O(N).

Optimal Solution

Approach

This problem asks us to rearrange a list of numbers and find their positions after each rearrangement. The trick is to avoid searching the entire list every time by keeping track of the numbers and their order efficiently. Instead of using a simple list, we'll use a structure that allows fast insertion and deletion in the middle.

Here's how the algorithm would work step-by-step:

Start with an ordered list of numbers from 1 to a given number.
For each query number, find where that number is currently located in your list.
Record the location of that number; this is your answer for that query.
Now, take that number out of the list.
Put that number back at the very beginning of the list.
Continue this process for all the query numbers. The list will be updated after each query to reflect the new order.

Code Implementation

def process_queries_on_permutation(queries, maximum_number):
    permutation_list = list(range(1, maximum_number + 1))
    result_list = []

    for query_value in queries:
        # Find the index of the query value
        index_of_query = permutation_list.index(query_value)
        result_list.append(index_of_query)

        # Remove the query value from its current position.
        permutation_list.pop(index_of_query)

        # Insert the query value at the beginning of the list.
        permutation_list.insert(0, query_value)

    return result_list

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through m queries. For each query, it searches for the element in a list of size n in the worst-case scenario. Removing the element then takes O(n) to shift the subsequent elements, and inserting at the beginning also takes O(n) to shift existing elements. Therefore, each query potentially takes O(n) + O(n) + O(n) = O(n) time. Since there are m queries, the total time complexity is O(m*n).

Space Complexity

O(m) – The auxiliary space complexity is determined by the initial ordered list of numbers from 1 to m (where m is the input integer). This list requires space proportional to m. After each query, the elements are rearranged within this same list; no new lists are created. Therefore, the algorithm uses O(m) auxiliary space to store the initial permutation.

Edge Cases

Case	How to Handle
Empty queries array	Return an empty result array, as there are no queries to process.
m is zero or negative	If m is zero, return an empty result list immediately since no permutation can be created; if m is negative throw an IllegalArgumentException as it is not a valid input.
Empty or Null queries	Throw IllegalArgumentException since queries is required.
Large m value that causes memory issues	Limit the maximum value of m to prevent excessive memory allocation, potentially throwing an exception if exceeded.
Queries contain duplicate values	The algorithm should handle duplicate query values correctly, as it finds and moves the first instance of the element during each query.
Queries contain numbers outside the range [1, m]	Filter out queries with values outside the range [1, m] or return -1 indicating an invalid query.
Large number of queries approaching a theoretical limit	The time complexity of the solution should be carefully analyzed, considering the worst-case scenario with a large number of queries, optimizing data structures or algorithms where possible.
m is close to the maximum integer value	Carefully assess potential integer overflow issues during indexing or calculations, using long data types if necessary to prevent unexpected behavior.

Empty queries array

How to Handle:

Return an empty result array, as there are no queries to process.

m is zero or negative

How to Handle:

If m is zero, return an empty result list immediately since no permutation can be created; if m is negative throw an IllegalArgumentException as it is not a valid input.

Empty or Null queries

How to Handle:

Throw IllegalArgumentException since queries is required.

Large m value that causes memory issues

How to Handle:

Limit the maximum value of m to prevent excessive memory allocation, potentially throwing an exception if exceeded.

Queries contain duplicate values

How to Handle:

The algorithm should handle duplicate query values correctly, as it finds and moves the first instance of the element during each query.

Queries contain numbers outside the range [1, m]

How to Handle:

Filter out queries with values outside the range [1, m] or return -1 indicating an invalid query.

Large number of queries approaching a theoretical limit

How to Handle:

The time complexity of the solution should be carefully analyzed, considering the worst-case scenario with a large number of queries, optimizing data structures or algorithms where possible.

m is close to the maximum integer value

How to Handle:

Carefully assess potential integer overflow issues during indexing or calculations, using long data types if necessary to prevent unexpected behavior.