Facebook Pixel

3109. Find the Index of Permutation 🔒

MediumBinary Indexed TreeSegment TreeArrayBinary SearchDivide and ConquerOrdered SetMerge Sort
Leetcode Link

Problem Description

Given an array perm of length n which is a permutation of [1, 2, ..., n], return the index of perm in the lexicographically sorted array of all the permutations of [1, 2, ..., n]. Since the answer may be very large, return it modulo (10^9 + 7).

Intuition

The task is to determine the index of a given permutation in the sorted list of all possible permutations. The concept revolves around counting the number of permutations that are lexicographically smaller than the given permutation.

Key Observations:

  1. Each position in the permutation can influence how many permutations are smaller. If the first element of the permutation is smaller than the current element, all permutations starting with those smaller elements need to be considered.

  2. For each position i in the permutation:

    • If the element at perm[i] is smaller compared to those remaining elements in the list, count those permutations multiply by the factorial of the remaining elements.

  3. To efficiently determine how many elements before the current element are smaller, use a Binary Indexed Tree (Fenwick Tree). This data structure allows updates in logarithmic time complexity, making it suitable for dynamic frequency counting.

  4. Update the count in the tree as you process each element of the permutation to ensure accuracy for subsequent comparisons.

Thus, by leveraging the factorial reduction for permutations and efficient counting of elements lower than the current one, you accurately compute the permutation's rank.

Learn more about Segment Tree, Binary Search, Divide and Conquer and Merge Sort patterns.

Solution Approach

The solution leverages the Binary Indexed Tree (BIT) data structure to efficiently manage prefix sums and updates, which are crucial for determining the number of elements smaller than the current one dynamically.

Steps in the Solution:

  1. Factorial Precomputation:

    • Precompute the factorials from 0 to n-1 since they're required for counting smaller permutations. Store these in an array f, where f[i] = i!.

  2. Binary Indexed Tree Initialization:

    • Initialize a Binary Indexed Tree to keep track of the count of encountered elements. This allows querying how many smaller elements are present at any point to the left efficiently.

  3. Iterative Calculation:

    • For each element in the permutation perm, compute the number of permutations that can be formed with smaller elements at the current position. For element perm[i]:
      • Use tree.query(perm[i]) to get the count of elements less than perm[i] encountered so far.
      • Calculate cnt = perm[i] - 1 - tree.query(perm[i]).
      • Update the permutation index: ans += cnt * f[n - i - 1] % mod.
      • Update the binary indexed tree with tree.update(perm[i], 1) to reflect that this element has been fully processed.

  4. Return Result Modulo 10^9 + 7:

    • Since the result can be very large, return ans % mod where mod is (10^9 + 7).

This approach efficiently calculates the permutation's index using logarithmic updates and queries in the binary indexed tree, ensuring a solution that can handle larger permutations without performance degradation.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the permutation perm = [3, 1, 2] for n = 3.

  1. Factorial Precomputation:

    • Compute the factorial values. For n = 3, we need f[0], f[1], f[2].
      • f[0] = 1! = 1
      • f[1] = 1! = 1
      • f[2] = 2! = 2
    • So, the factorial array is f = [1, 1, 2].

  2. Binary Indexed Tree Initialization:

    • Initialize the Binary Indexed Tree (BIT) to handle elements from 1 to n (i.e., 1 to 3).

  3. Iterative Calculation:

    • Initialize ans = 0 to accumulate the permutation's index.

    • First Position (i = 0, perm[i] = 3):

      • Use tree.query(3) to find how many elements smaller than 3 have been encountered. The result is 0 since no elements have been processed yet.
      • Calculate cnt = 3 - 1 - 0 = 2.
      • Update ans = ans + (cnt * f[n - i - 1]) % mod = (0 + 2 * f[2]) % mod = 4.
      • Update the BIT with tree.update(3, 1) to mark 3 as processed.

    • Second Position (i = 1, perm[i] = 1):

      • Use tree.query(1) to find the count of elements smaller than 1. The result is 0.
      • Calculate cnt = 1 - 1 - 0 = 0.
      • Update ans = ans + (cnt * f[n - i - 1]) % mod = (4 + 0 * f[1]) % mod = 4.
      • Update the BIT with tree.update(1, 1).

    • Third Position (i = 2, perm[i] = 2):

      • Use tree.query(2) to find how many elements smaller than 2 are encountered. The result is 1 because 1 is already processed.
      • Calculate cnt = 2 - 1 - 1 = 0.
      • Update ans = ans + (cnt * f[n - i - 1]) % mod = (4 + 0 * f[0]) % mod = 4.
      • Update BIT with tree.update(2, 1).

  4. Return Result:

    • The final index is ans % mod = 4 % (10^9 + 7) = 4.

Thus, the lexicographical index of the permutation [3, 1, 2] in all permutations of [1, 2, 3] is 4.

Solution Implementation

1from typing import List
2
3class BinaryIndexedTree:
4    __slots__ = "n", "c"
5
6    def __init__(self, n: int):
7        # Initialize the size of tree and an auxiliary array `c` with size n+1
8        self.n = n
9        self.c = [0] * (n + 1)
10
11    def update(self, x: int, delta: int) -> None:
12        # Update the Binary Indexed Tree by adding `delta` to index `x`.
13        while x <= self.n:
14            self.c[x] += delta
15            x += x & -x  # Move to the next responsible index
16
17    def query(self, x: int) -> int:
18        # Query the prefix sum from 1 to `x`.
19        sum_ = 0
20        while x > 0:
21            sum_ += self.c[x]
22            x -= x & -x  # Move to the parent index
23        return sum_
24
25
26class Solution:
27    def getPermutationIndex(self, perm: List[int]) -> int:
28        mod = 10**9 + 7  # A large prime number for modulo operations
29        ans, n = 0, len(perm)
30      
31        # Initialize a Binary Indexed Tree (BIT) with size n+1
32        bit_tree = BinaryIndexedTree(n + 1)
33      
34        # Precompute factorials modulo `mod`
35        factorial = [1] * n
36        for i in range(1, n):
37            factorial[i] = factorial[i - 1] * i % mod
38      
39        # Calculate the permutation index
40        for i, value in enumerate(perm):
41            # Count how many numbers smaller than `value` are already placed
42            count = value - 1 - bit_tree.query(value)
43          
44            # Increment the answer by the number of permutations that can be formed with smaller elements in this position
45            ans += count * factorial[n - i - 1] % mod
46          
47            # Update the BIT for the element `value`
48            bit_tree.update(value, 1)
49      
50        return ans % mod  # Return the result modulo `mod`
51
1// A class representing the Binary Indexed Tree (Fenwick Tree) data structure
2class BinaryIndexedTree {
3    private int size;
4    private int[] treeArray;
5  
6    // Constructor to initialize the tree with a specified size
7    public BinaryIndexedTree(int size) {
8        this.size = size;
9        this.treeArray = new int[size + 1];
10    }
11  
12    // Method to update the value at a specific position
13    public void update(int position, int delta) {
14        // Update the tree path with the given delta value
15        for (; position <= size; position += position & -position) {
16            treeArray[position] += delta;
17        }
18    }
19  
20    // Method to query the cumulative frequency up to a specific position
21    public int query(int position) {
22        int result = 0;
23        // Traverse the tree in reverse to accumulate results
24        for (; position > 0; position -= position & -position) {
25            result += treeArray[position];
26        }
27        return result;
28    }
29}
30
31// A class containing a method to find the permutation index
32class Solution {
33  
34    // Function to calculate the lexicographical index of a given permutation
35    public int getPermutationIndex(int[] perm) {
36        final int MODULO = (int) 1e9 + 7; // To handle large numbers
37        long index = 0; // Variable to store the permutation index
38        int n = perm.length; // Length of the permutation array
39      
40        // Initialize the Binary Indexed Tree with size n + 1
41        BinaryIndexedTree bit = new BinaryIndexedTree(n + 1);
42      
43        // Array to store factorial values efficiently (modulo MODULO)
44        long[] factorial = new long[n];
45        factorial[0] = 1;
46        for (int i = 1; i < n; ++i) {
47            factorial[i] = factorial[i - 1] * i % MODULO;
48        }
49      
50        // Calculate the index of the permutation
51        for (int i = 0; i < n; ++i) {
52            int count = perm[i] - 1 - bit.query(perm[i]);
53            index = (index + count * factorial[n - i - 1] % MODULO) % MODULO;
54            bit.update(perm[i], 1); // Mark this number as used in the BIT
55        }
56      
57        // Return the calculated index as an integer
58        return (int) index;
59    }
60}
61
1#include <vector>
2using namespace std;
3
4// Implementation of Binary Indexed Tree (Fenwick Tree)
5class BinaryIndexedTree {
6private:
7    int n;              // size of the array
8    vector<int> c;      // internal tree array for cumulative frequencies
9
10public:
11    // Constructor initializes the tree with the specified size
12    BinaryIndexedTree(int n)
13        : n(n), c(n + 1) {} // Initialize vector size n + 1 as we use 1-based index
14
15    // Update function adjusts values at index x by delta
16    void update(int x, int delta) {
17        for (; x <= n; x += x & -x) {
18            c[x] += delta; // Increment all affected indices
19        }
20    }
21
22    // Query function returns the prefix sum up to index x
23    int query(int x) {
24        int sum = 0;
25        for (; x > 0; x -= x & -x) {
26            sum += c[x]; // Accumulate the results from the Fenwick Tree
27        }
28        return sum;
29    }
30};
31
32class Solution {
33public:
34    // Function to find the permutation index of the permutation vector
35    int getPermutationIndex(vector<int>& perm) {
36        const int mod = 1e9 + 7;           // Modulo for large numbers
37        using ll = long long;              // For handling large factorial results
38        ll ans = 0;                        // Result variable
39        int n = perm.size();               // Size of the permutation
40
41        BinaryIndexedTree tree(n + 1);     // Initialize the BIT/Fenwick Tree
42        ll f[n];                           // Array to store factorials modulo 'mod'
43        f[0] = 1;                          // Base case factorial of 0 is 1
44      
45        // Calculate factorials modulo 'mod'
46        for (int i = 1; i < n; ++i) {
47            f[i] = f[i - 1] * i % mod;     // Next factorial calculated based on the previous one
48        }
49
50        // Calculate the lexicographic order of the permutation
51        for (int i = 0; i < n; ++i) {
52            // Calculate the number of permutations bypassed by counting numbers smaller than perm[i]
53            int cnt = perm[i] - 1 - tree.query(perm[i]);
54            ans = (ans + cnt * f[n - i - 1] % mod) % mod; // Increment the result accordingly
55            tree.update(perm[i], 1);       // Update the binary indexed tree
56        }
57      
58        return ans;
59    }
60};
61
1// Function to create and manage a Binary Indexed Tree (BIT) data structure
2function createBinaryIndexedTree(n: number) {
3    const c = Array(n + 1).fill(0); // Initialize an array for the BIT, size n + 1
4
5    // Method to update the BIT at position x by a given delta
6    function update(x: number, delta: number): void {
7        for (; x <= n; x += x & -x) {
8            c[x] += delta;
9        }
10    }
11
12    // Method to get the prefix sum up to position x
13    function query(x: number): number {
14        let s = 0;
15        for (; x > 0; x -= x & -x) {
16            s += c[x];
17        }
18        return s;
19    }
20
21    return { update, query };
22}
23
24// Function to calculate the permutation index
25function getPermutationIndex(perm: number[]): number {
26    const mod = 1e9 + 7; // Define the modulo value for calculating the result
27    const n = perm.length; // Get the length of the permutation array
28    const tree = createBinaryIndexedTree(n + 1); // Instantiate the BIT with size n + 1
29    let ans = 0; // Variable to store the final permutation index result
30  
31    // Array to store factorial values
32    const f: number[] = Array(n).fill(1);
33    for (let i = 1; i < n; ++i) {
34        f[i] = (f[i - 1] * i) % mod; // Compute factorials modulo mod
35    }
36
37    // Iterate through each element in the permutation
38    for (let i = 0; i < n; ++i) {
39        // Calculate how many numbers are smaller than perm[i] that have not been placed yet
40        const cnt = perm[i] - 1 - tree.query(perm[i]);
41      
42        // Update the permutation index using the factorial of remaining items
43        ans = (ans + cnt * f[n - i - 1]) % mod;
44
45        // Update the BIT to mark perm[i] as used
46        tree.update(perm[i], 1);
47    }
48  
49    return ans % mod;
50}
51

Time and Space Complexity

The time complexity of the code is O(n \times \log n). This complexity arises because the update and query operations of the BinaryIndexedTree both have a time complexity of O(\log n). Each element of the permutation is processed once with these operations, leading to an overall time complexity of O(n \times \log n).

The space complexity of the code is O(n). This is due to the BinaryIndexedTree storing an array c of size n + 1, and the array f storing factorial values up to n, both of which require O(n) space.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

In a binary min heap, the maximum element can be found in:

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More