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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Queries on a Permutation With Key

Number: 1525

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of queries where each query is an integer between 1 and m, we start with a permutation P = [1, 2, 3, ..., m]. For each query, find the current index of the queried number in P, record that index, and then move the number to the beginning of the list. Return an array that contains the recorded indices for each query.

Key Insights

  • We simulate the operations on the permutation P.
  • Finding the index of a number in the list and then moving it to the front is straightforward.
  • Although a naive list simulation works due to small constraints (m ≤ 10^3), more efficient approaches (like using a Binary Indexed Tree) can be employed for larger inputs.
  • The challenge is to update the permutation and measure the index positions effectively.

Space and Time Complexity

Time Complexity: O(n * m) in the worst-case using simple list operations (where n is the number of queries). Optimized solutions using BIT can achieve O(n log m). Space Complexity: O(m) for storing the permutation.

Solution

The solution is to simulate the permutation operations as described. We maintain the permutation using a list (or equivalent data structure). For each query, we:

  1. Find the index of the queried number in the current permutation.
  2. Append this index to the result.
  3. Remove the number from its current position.
  4. Insert the number at the beginning of the permutation. This straightforward simulation uses list operations that are sufficient given the problem constraints. Additional data structures like Binary Indexed Trees can be used to optimize the index fetching and updating for larger constraints.

Code Solutions

# Function to process the queries and return index results
def processQueries(queries, m):
    # Initialize the permutation list with numbers 1 to m
    permutation = list(range(1, m + 1))
    result = []
    # Process each query
    for query in queries:
        # Find the index of the query in the current permutation
        index = permutation.index(query)
        # Append the found index to the result list
        result.append(index)
        # Remove the query number from its current position
        permutation.pop(index)
        # Insert the query number at the beginning of the permutation
        permutation.insert(0, query)
    return result

# Example test case
queries = [3, 1, 2, 1]
m = 5
print(processQueries(queries, m))  # Expected output: [2, 1, 2, 1]
← Back to All Questions