1409. Queries on a Permutation With Key LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1409. Queries on a Permutation With Key LeetCode Solution with the best time and space complexity. The solution to Queries on a Permutation With Key problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Queries on a Permutation With Key solution in C++
Queries on a Permutation With Key solution in Java
Queries on a Permutation With Key solution in Python
Additional Resources

1409. Queries on a Permutation With Key LeetCode Solution image

Problem Statement of Queries on a Permutation With Key

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

Complexity Analysis

Time Complexity: O(q\log m)
Space Complexity: O(q + m)

1409. Queries on a Permutation With Key LeetCode Solution in C++

class FenwickTree {
 public:
  FenwickTree(int n) : sums(n + 1) {}

  void add(int i, int delta) {
    while (i < sums.size()) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  int get(int i) const {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

 private:
  vector<int> sums;

  static inline int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  vector<int> processQueries(vector<int>& queries, int m) {
    vector<int> ans;
    // Map [-m, m] to [0, 2 * m].
    FenwickTree tree(2 * m + 1);
    unordered_map<int, int> numToIndex;

    for (int num = 1; num <= m; ++num) {
      numToIndex[num] = num + m;
      tree.add(num + m, 1);
    }

    int nextEmptyIndex = m;  // Map 0 to m.

    for (const int query : queries) {
      const int index = numToIndex[query];
      ans.push_back(tree.get(index - 1));
      // Move `query` from `index` to `nextEmptyIndex`.
      tree.add(index, -1);
      tree.add(nextEmptyIndex, 1);
      numToIndex[query] = nextEmptyIndex--;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1409. Queries on a Permutation With Key LeetCode Solution in Java

class FenwickTree {
  public FenwickTree(int n) {
    sums = new int[n + 1];
  }

  public void add(int i, int delta) {
    while (i < sums.length) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  public int get(int i) {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

  private int[] sums;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public int[] processQueries(int[] queries, int m) {
    int[] ans = new int[queries.length];
    // Map [-m, m] to [0, 2 * m].
    FenwickTree tree = new FenwickTree(2 * m + 1);
    Map<Integer, Integer> numToIndex = new HashMap<>();

    for (int num = 1; num <= m; ++num) {
      numToIndex.put(num, num + m);
      tree.add(num + m, 1);
    }

    int nextEmptyIndex = m; // Map 0 to m.

    for (int i = 0; i < queries.length; ++i) {
      final int query = queries[i];
      final int index = numToIndex.get(query);
      ans[i] = tree.get(index - 1);
      // Move `query` from `index` to `nextEmptyIndex`.
      tree.add(index, -1);
      tree.add(nextEmptyIndex, 1);
      numToIndex.put(query, nextEmptyIndex--);
    }

    return ans;
  }
}
// code provided by PROGIEZ

1409. Queries on a Permutation With Key LeetCode Solution in Python

class FenwickTree:
  def __init__(self, n: int):
    self.sums = [0] * (n + 1)

  def add(self, i: int, delta: int) -> None:
    while i < len(self.sums):
      self.sums[i] += delta
      i += FenwickTree.lowbit(i)

  def get(self, i: int) -> int:
    summ = 0
    while i > 0:
      summ += self.sums[i]
      i -= FenwickTree.lowbit(i)
    return summ

  @staticmethod
  def lowbit(i: int) -> int:
    return i & -i


class Solution:
  def processQueries(self, queries: list[int], m: int) -> list[int]:
    ans = []
    # Map [-m, m] to [0, 2 * m].
    tree = FenwickTree(2 * m + 1)
    numToIndex = {num: num + m for num in range(1, m + 1)}

    for num in range(1, m + 1):
      tree.add(num + m, 1)

    nextEmptyIndex = m  # Map 0 to m.

    for query in queries:
      index = numToIndex[query]
      ans.append(tree.get(index - 1))
      # Move `query` from `index` to `nextEmptyIndex`.
      tree.add(index, -1)
      tree.add(nextEmptyIndex, 1)
      numToIndex[query] = nextEmptyIndex
      nextEmptyIndex -= 1

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents