medium Queries on a Permutation With Key

Problem Statement

You are given a list called queries, containing positive integers between 1 and m. You need to process each number in queries according to the following rules:

• Start with a sequence P which is [1, 2, 3, ..., m].
• For each number in queries list, find its current position in P (0-based index), then move this number to the front of P. Notice that the position of queries[i] in P is the result for queries[i].

Return a list of results in the order corresponding to the numbers in queries.

Examples

Example 1:

• Input: queries = [4, 3, 2, 7, 5], m = 7
• Output: [3,3,3,6,5]
• Explanation:
  • Initially, P = [1, 2, 3, 4, 5, 6, 7].
  • For 4, position is 3, move 4 to front, P = [4, 1, 2, 3, 5, 6, 7].
  • For 3, position is 3, move 3 to front, P = [3, 4, 1, 2, 5, 6, 7].
  • For 2, position is 3, move 2 to front, P = [2, 3, 4, 1, 5, 6, 7].
  • For 7, position is 6, move 7 to front, P = [7, 2, 3, 4, 1, 5, 6].
  • For 5, position is 5, move 5 to front, P = [5, 7, 2, 3, 4, 1, 6].

Example 2:

• Input: queries = [1, 6, 3, 6], m = 6
• Output: [0, 5, 3, 1]
• Explanation:
  • Initially, P = [1, 2, 3, 4, 5, 6].
  • For 1, position is 0, move 1 to front, P = [1, 2, 3, 4, 5, 6].
  • For 6, position is 5, move 6 to front, P = [6, 1, 2, 3, 4, 5].
  • For 3, position is 3, move 3 to front, P = [3, 6, 1, 2, 4, 5].
  • For 6, position is 1, move 6 to front, P = [6, 3, 1, 2, 4, 5].

Example 3:

• Input: queries = [5, 1, 2, 4, 1], m = 5
• Output: [4,1,2,4,2]
• Explanation:
  • Initially, P = [1, 2, 3, 4, 5].
  • For 5, position is 4, move 5 to front, P = [5, 1, 2, 3, 4].
  • For 1, position is 1, move 1 to front, P = [1, 5, 2, 3, 4].
  • For 2, position is 2, move 2 to front, P = [2, 1, 5, 3, 4].
  • For 4, position is 4, move 4 to front, P = [4, 2, 1, 5, 3].
  • For 1, position is 2, move 1 to front, P = [1, 4, 2, 5, 3].

Constraints:

• 1 <= m <= 10³
• 1 <= queries.length <= m
• 1 <= queries[i] <= m

Solution

To solve the problem using the Binary Indexed Tree (BIT), we begin by initializing an array that holds the position of each element in the permutation. We also create a BIT array with a size of (m + n + 1), where (m) is the size of the permutation and (n) is the length of the queries. The BIT allows us to efficiently calculate prefix sums and update values, which helps in finding the current position of any element in the permutation and moving it to the front of the list.

The solution works by iterating through each query, using the BIT to find the current position of the queried element. After identifying its position, we update the BIT to remove the element from its current position and move it to the front. This is achieved by decrementing the value at the element's current position in the BIT and incrementing the value at the front of the permutation in the BIT. We then adjust the position of the element in the position array to reflect its new position at the front of the permutation. The process is repeated for each query, and the results are stored in a list.

Step-by-Step Algorithm

1. Initialization of Arrays:

   • Create an array position of size m + 1. This array is used to store the current position of each element in the permutation P. We add 1 to the size because we're indexing elements from 1 to m instead of 0.
   • Create a Binary Indexed Tree (BIT) array of size m + n + 1. The size m + n + 1 is chosen to accommodate both the elements in the permutation and the queries. The BIT is used for efficient prefix sum calculations and updates.

2. Build the Initial BIT:

   • Loop through each element from 1 to m:
     • For each element i, set position[i] = n + i. This places the elements of P after all the queries in the BIT. For example, if n = 4 and m = 7, the positions will be set as [5, 6, 7, 8, 9, 10, 11].
     • Call the updateBIT method with the index n + i and the value 1. This step initializes the BIT by adding 1 to the affected nodes in the BIT array. The update propagates this change through the tree, ensuring that the BIT correctly represents the presence of each element in the permutation.

3. Processing Each Query:

   • For each query element q in the queries array:

     1. Find the Current Position:

        • Call the getPrefixSum method with position[q] - 1 to calculate the number of elements before the current position of q. This method sums up the values in the BIT from the start up to position[q] - 1, effectively determining the 0-based index of q in the current permutation.
        • The result from getPrefixSum is added to the result list, which represents the index of q before it is moved to the front.

     2. Update the BIT for Removal:

        • Call the updateBIT method with position[q] and -1 as arguments. This operation subtracts 1 from the BIT at the current position of q, effectively "removing" the element from its current spot in the permutation. This is necessary because q will be moved to the front, and the BIT must reflect this change.

     3. Move the Element to the Front:

        • Call the updateBIT method with n and 1 as arguments. This operation adds 1 to the BIT at the index n, indicating that the element q is now placed at the front of the permutation.
        • Update the position[q] to n, and then decrement n by 1. This step assigns the new front position to q and prepares n for the next query. Decreasing n ensures that subsequent elements are placed at the correct positions closer to the front.

4. Return the Result:

   • Once all queries are processed, the result list containing the positions of the queried elements before they were moved is returned.

Explanation of Methods:

1. updateBIT Method:

   • This method updates the BIT at a specific index by a given value (val). It iteratively adds the value to the BIT and propagates the update to the affected nodes in the tree structure, ensuring that future prefix sum queries correctly account for this change.
   • The reason for passing 1 as the value during the initialization is to incrementally build the BIT structure, indicating the presence of each element in the permutation. When -1 is passed, it effectively "removes" the element from its current position by decrementing the relevant nodes in the BIT.

2. getPrefixSum Method:

   • The getPrefixSum method calculates the sum of values in the BIT up to a specific index. This sum represents the number of elements in the permutation that precede the queried element. By summing the values, the method efficiently determines the position of the element in the current permutation.

3. Position Update:

   • The line position[q] = n--; updates the position of the queried element q to the front of the permutation. The decrement n-- ensures that the next queried element will be placed in the next available position closer to the front. This maintains the correct ordering of elements as they are moved to the front in sequence.

Algorithm Walkthrough

Let's walk through the algorithm with queries = [4, 3, 2, 7, 5] and m = 7. We'll explain each step in detail, especially for the first two queries.

1. Initialization:

• We start by initializing the position array and the BIT array.
• The position array is initialized as follows, with elements indexed from 1 to 7 (since m = 7):
  • position = [ , 6, 7, 8, 9, 10, 11, 12]
  • The positions start from n + 1 (where n = 5, the length of the queries array), so position[i] = n + i.

2. Build Initial BIT:

• We initialize the BIT array by iterating over each element in the permutation (i from 1 to m). We call the updateBIT method for each position[i] with the value 1 to build the initial BIT.

• Step-by-step update for each i:

  • For i = 1:

    • position[1] = 6
    • updateBIT(BIT, 6, 1) updates the BIT array.
    • Affected nodes:
      • index = 6: Add 1 to BIT[6] → BIT[6] = 1.
      • index = 8: Add 1 to BIT[8] → BIT[8] = 1.
      • index = 16: Out of range, stop.

  • For i = 2:

    • position[2] = 7
    • updateBIT(BIT, 7, 1) updates the BIT array.
    • Affected nodes:
      • index = 7: Add 1 to BIT[7] → BIT[7] = 1.
      • index = 8: Add 1 to BIT[8] → BIT[8] = 2.
      • index = 16: Out of range, stop.

  • For i = 3:

    • position[3] = 8
    • updateBIT(BIT, 8, 1) updates the BIT array.
    • Affected nodes:
      • index = 8: Add 1 to BIT[8] → BIT[8] = 3.
      • index = 16: Out of range, stop.

  • For i = 4:

    • position[4] = 9
    • updateBIT(BIT, 9, 1) updates the BIT array.
    • Affected nodes:
      • index = 9: Add 1 to BIT[9] → BIT[9] = 1.
      • index = 10: Add 1 to BIT[10] → BIT[10] = 1.
      • index = 12: Add 1 to BIT[12] → BIT[12] = 1.
      • index = 16: Out of range, stop.

  • For i = 5:

    • position[5] = 10
    • updateBIT(BIT, 10, 1) updates the BIT array.
    • Affected nodes:
      • index = 10: Add 1 to BIT[10] → BIT[10] = 2.
      • index = 12: Add 1 to BIT[12] → BIT[12] = 2.
      • index = 16: Out of range, stop.

  • For i = 6:

    • position[6] = 11
    • updateBIT(BIT, 11, 1) updates the BIT array.
    • Affected nodes:
      • index = 11: Add 1 to BIT[11] → BIT[11] = 1.
      • index = 12: Add 1 to BIT[12] → BIT[12] = 3.
      • index = 16: Out of range, stop.

  • For i = 7:

    • position[7] = 12
    • updateBIT(BIT, 12, 1) updates the BIT array.
    • Affected nodes:
      • index = 12: Add 1 to BIT[12] → BIT[12] = 4.
      • index = 16: Out of range, stop.

• Final BIT array after initialization:

  [0, 0, 0, 0, 0, 0, 1, 1, 3, 1, 2, 1, 4]
  

Processing Each Query

Now, let's process each query step-by-step. We'll go into detail for the first two queries.

Query 1: q = 4

1. Find the Current Position:

   • Call getPrefixSum(BIT, position[4] - 1).
   • Here, position[4] = 9, so we call getPrefixSum(BIT, 8).
   • getPrefixSum Execution:
     • Start at index = 8:
       • Add BIT[8] = 3 to sum → sum = 3.
       • Update index = 8 - (8 & -8) = 0.
       • index = 0, out of range, stop.
     • The result of getPrefixSum is 3, so the position of 4 is 3 (0-based).

2. Update BIT for Removal of 4:

   • Call updateBIT(BIT, position[4], -1).
   • Here, position[4] = 9.
   • updateBIT Execution:
     • Start at index = 9:
       • Subtract 1 from BIT[9] → BIT[9] = 0.
       • Update index = 9 + (9 & -9) = 10.
     • At index = 10:
       • Subtract 1 from BIT[10] → BIT[10] = 1.
       • Update index = 12.
     • At index = 12:
       • Subtract 1 from BIT[12] → BIT[12] = 3.
       • Update index = 16.
       • index = 16, out of range, stop.
   • BIT array after removal of 4:

     [0, 0, 0, 0, 0, 0, 1, 1, 3, 0, 1, 1, 3]
     

3. Move 4 to the Front:

   • Call updateBIT(BIT, n, 1) to move 4 to the front.
   • Here, n = 5.
   • updateBIT Execution:
     • Start at index = 5:
       • Add 1 to BIT[5] → BIT[5] = 1.
       • Update index = 6.
     • At index = 6:
       • Add 1 to BIT[6] → BIT[6] = 2.
       • Update index = 8.
     • At index = 8:
       • Add 1 to BIT[8] → BIT[8] = 4.
       • Update index = 16.
       • index = 16, out of range, stop.
   • BIT array after moving 4 to the front:

     [0, 0, 0, 0, 0, 1, 2, 1, 4, 0, 1, 1, 3]
     

   • Update position[4] = n (set position[4] = 5), then decrement n to 4.

Query 2: q = 3

1. Find the Current Position:

   • Call getPrefixSum(BIT, position[3] - 1).
   • Here, position[3] = 8, so we call getPrefixSum(BIT, 7).
   • getPrefixSum Execution:
     • Start at index = 7:
       • Add BIT[7] = 1 to sum → sum = 1.
       • Update index = 6.
     • At index = 6:
       • Add BIT[6] = 2 to sum → sum = 3.
       • Update index = 4.
       • index = 4, out of range, stop.
     • The result of getPrefixSum is 3, so the position of 3 is 3 (0-based).

2. Update BIT for Removal of 3:

   • Call updateBIT(BIT, position[3], -1).
   • Here, position[3] = 8.
   • updateBIT Execution:
     • Start at index = 8:
       • Subtract 1 from BIT[8] → BIT[8] = 3.
       • Update index = 16.
       • index = 16, out of range, stop.
   • BIT array after removal of 3:

     [0, 0, 0, 0, 0, 1, 2, 1, 3, 0, 1, 1, 3]
     

3. Move 3 to the Front:

   • Call updateBIT(BIT, n, 1) to move 3 to the front.
   • Here, n = 4.
   • updateBIT Execution:
     • Start at index = 4:
       • Add 1 to BIT[4] → BIT[4] = 1.
       • Update index = 8.
     • At index = 8:
       • Add 1 to BIT[8] → BIT[8] = 4.
       • Update index = 16.
       • index = 16, out of range, stop.
   • BIT array after moving 3 to the front:

     [0, 0, 0, 0, 1, 1, 2, 1, 4, 0, 1, 1, 3]
     

   • Update position[3] = n (set position[3] = 4), then decrement n to 3.

This way process all queries and you will get [3, 3, 3, 6, 5] as a result array.

Code

import java.util.ArrayList;
import java.util.List;

class Solution {

  // Method to calculate the prefix sum up to index 'index' using BIT
  private int getPrefixSum(int[] BIT, int index) {
    int sum = 0;
    // Traverse the BIT array backward to calculate the sum
    for (; index > 0; index -= (index & -index)) {
      sum += BIT[index];
    }
    return sum;
  }

  // Method to update the BIT array at index 'index' with a value val
  private void updateBIT(int[] BIT, int index, int val) {
    // Traverse the BIT array forward to update the values
    for (; index < BIT.length; index += (index & -index)) {
      BIT[index] += val;
    }
  }

  // Main method to process the queries
  public List<Integer> processQueries(int[] queries, int m) {
    int n = queries.length;
    List<Integer> result = new ArrayList<>(); // List to store the final result
    int[] BIT = new int[m + n + 1]; // Binary Indexed Tree with size m + n + 1
    int[] position = new int[m + 1]; // Array to store the position of each element

    // Initialize the position array and build the initial BIT
    for (int i = 1; i <= m; i++) {
      position[i] = n + i; // Position starts after the queries array
      updateBIT(BIT, n + i, 1); // Build the BIT by adding initial elements
    }

    // Process each query
    for (int q : queries) {
      // Get the current position of the query element
      result.add(getPrefixSum(BIT, position[q] - 1));
      // Update the BIT to remove the element from its current position
      updateBIT(BIT, position[q], -1);
      // Update the BIT to move the element to the front
      updateBIT(BIT, n, 1);
      // Update the position of the element to the new position (front)
      position[q] = n--;
    }

    return result; // Return the result list
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] queries1 = { 4, 3, 2, 7, 5 };
    int m1 = 7;
    List<Integer> result1 = solution.processQueries(queries1, m1);
    System.out.println(result1); // Output: [3, 3, 3, 6, 5]

    // Example 2
    int[] queries2 = { 1, 6, 3, 6 };
    int m2 = 6;
    List<Integer> result2 = solution.processQueries(queries2, m2);
    System.out.println(result2); // Output: [0, 5, 3, 1]

    // Example 3
    int[] queries3 = { 5, 1, 2, 4, 1 };
    int m3 = 5;
    List<Integer> result3 = solution.processQueries(queries3, m3);
    System.out.println(result3); // Output: [4, 1, 2, 4, 2]
  }
}

Updated Complexity Analysis

Time Complexity

• Initialization:

  • Initializing the position array and building the initial BIT takes time, where (m) is the size of the permutation.
  • The BIT array is initialized with a size of , where (n) is the length of the queries array. The complexity for building the BIT is because each update operation to the BIT takes time.

• Processing Queries:

  • For each query, finding the position using getPrefixSum involves querying the BIT, which takes time.
  • Updating the BIT (both removal and insertion) also takes for each operation.
  • Given that there are (n) queries, the overall time complexity for processing the queries is .

Thus, the overall time complexity of the solution is:

Space Complexity

• The space complexity is determined by the BIT and position arrays.
  • The BIT array requires space.
  • The position array requires space.

Thus, the overall space complexity is: