We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Queries on a Permutation With Key

Difficulty: Medium

Problem Description

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.

Key Insights

  • We start with a permutation of integers from 1 to m.
  • Each query requires finding an element's index and moving it to the front of the permutation.
  • The problem involves simulating the movement of elements in an array and maintaining their order based on the queries.

Space and Time Complexity

Time Complexity: O(n * m) in the worst case, where n is the length of queries and m is the size of the permutation.
Space Complexity: O(m) for storing the permutation.

Solution

The problem can be solved using a simple simulation approach. We maintain a list representing the current permutation. For each query, we find the index of the queried number in the list, store the index as the result, and then move that number to the front of the list. This can be efficiently handled using a list data structure.

  1. Initialize the permutation P as a list containing integers from 1 to m.
  2. For each query in queries:
    • Find the index of the queried number in P.
    • Store the index in the results array.
    • Move the queried number to the front of P by removing it from its current position and inserting it at the start.
  3. Return the results array.

Code Solutions

def processQueries(queries, m):
    P = list(range(1, m + 1))  # Initialize the permutation
    result = []
    
    for query in queries:
        index = P.index(query)  # Find the index of the query in P
        result.append(index)     # Store the index in result
        P.insert(0, P.pop(index))  # Move the queried number to the front
    
    return result
← Back to All Questions