Queries on a Permutation With Key - Practice Coding Problems

Queries on a Permutation With Key - Problem

Given an array queries of positive integers between 1 and m, you need to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

Initial Setup: You start with the permutation P = [1, 2, 3, ..., m].

Processing Rule: For the current query queries[i]:

Find the position of queries[i] in the permutation P (indexing from 0)
Move this element to the beginning of the permutation P
The position found is the result for queries[i]

Return an array containing the result for all given queries.

Input & Output

Example 1 — Basic Case

$ Input: queries = [3,1,2,1], m = 5

› Output: [2,1,1,0]

💡 Note: Start: P=[1,2,3,4,5]. Query 3: position 2, P=[3,1,2,4,5]. Query 1: position 1, P=[1,3,2,4,5]. Query 2: position 2, P=[2,1,3,4,5]. Query 1: position 1, P=[1,2,3,4,5].

Example 2 — Single Query

$ Input: queries = [4], m = 4

› Output: [3]

💡 Note: Start: P=[1,2,3,4]. Query 4: position 3, P=[4,1,2,3]. Result is [3].

Example 3 — Repeated First Element

$ Input: queries = [1,1,1], m = 3

› Output: [0,0,0]

💡 Note: Start: P=[1,2,3]. All queries ask for element 1 which is always at position 0 after first query.

Constraints

1 ≤ queries.length, m ≤ 10³
1 ≤ queries[i] ≤ m

Visualization

Tap to expand

Understanding the Visualization

Input

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

Process

For each query, find position then move to front

Output

Array of positions: [2,1,1,0]

Key Takeaway

🎯 Key Insight: Each query returns the current position of the element, then moves it to the front, shifting all elements that were before it one position to the right.

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is simulating the move-to-front operation efficiently. The brute force approach directly maintains the permutation array and simulates each move operation. For each query, find the element's position, record it as the result, then move the element to the front. Best approach uses array simulation: Time: O(n×m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Position Tracking with Map	O(n×m)	O(m)	Track positions using a map and update positions efficiently
Simulation with Array	O(n×m)	O(m)	Simulate the process by maintaining the actual permutation array

Position Tracking with Map — Algorithm Steps

Step 1: Initialize position map: {1→0, 2→1, 3→2, ...}
Step 2: For each query, get current position from map
Step 3: Increment positions of elements that were before it
Step 4: Set queried element's position to 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Position Map

Track current position of each element

Query Processing

Get position, update others, move to front

Updated Map

Positions reflect the new order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* queries, int queriesSize, int m, int* returnSize) {
    // Initialize position array (simulating map)
    int* pos = (int*)malloc((m+1) * sizeof(int));
    for (int i = 1; i <= m; i++) {
        pos[i] = i - 1;
    }
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int query = queries[i];
        // Get current position
        int currPos = pos[query];
        result[i] = currPos;
        
        // Update positions: increment all elements that were before this one
        for (int j = 1; j <= m; j++) {
            if (pos[j] < currPos) {
                pos[j]++;
            }
        }
        
        // Move queried element to front
        pos[query] = 0;
    }
    
    free(pos);
    return result;
}

int main() {
    // Read queries array
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int queries[1000];
    int queriesSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        queries[queriesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int m;
    scanf("%d", &m);
    
    int returnSize;
    int* result = solution(queries, queriesSize, m, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each query, we may need to update positions of up to m elements

✓ Linear Growth

Space Complexity

O(m)

Hash map to store positions of m elements

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Position Tracking with Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler