Problem

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 of the permutations of [1, 2, ..., n].

Since the answer may be very large, return it modulo 109 + 7.

Examples

Example 1:

1
2
3
4
5
6

Input: perm = [1,2]
Output: 0
Explanation:
There are only two permutations in the following order:
`[1,2]`, `[2,1]`  
And `[1,2]` is at index 0.

Example 2:

1
2
3
4
5
6

Input: perm = [3,1,2]
Output: 4
Explanation:
There are only six permutations in the following order:
`[1,2,3]`, `[1,3,2]`, `[2,1,3]`, `[2,3,1]`, `[3,1,2]`, `[3,2,1]`  
And `[3,1,2]` is at index 4.

Constraints:

  • 1 <= n == perm.length <= 10^5
  • perm is a permutation of [1, 2, ..., n].

Solution

Method 1 – Factorial Number System (Lehmer Code)

Intuition

The index of a permutation in lexicographical order can be found by counting, for each position, how many smaller numbers remain to the right. This is efficiently computed using the factorial number system (Lehmer code) and a Fenwick Tree (BIT) for fast prefix sums.

Approach

  1. Initialize a Fenwick Tree (BIT) of size n to keep track of used numbers.
  2. For each position i in perm:
    • Count how many numbers less than perm[i] are still unused (using BIT).
    • The contribution to the index is count * (n-1-i)!
    • Mark perm[i] as used in the BIT.
  3. Sum all contributions and return (index + 1) % MOD (since index is 0-based).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int findPermutationIndex(vector<int>& perm) {
        const int MOD = 1e9 + 7;
        int n = perm.size();
        vector<int> bit(n+2, 0);
        auto add = [&](int x) { for (; x <= n; x += x & -x) bit[x] += 1; };
        auto sum = [&](int x) { int s = 0; for (; x; x -= x & -x) s += bit[x]; return s; };
        vector<long long> fact(n+1, 1);
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i % MOD;
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            int cnt = perm[i] - 1 - sum(perm[i] - 1);
            idx = (idx + 1LL * cnt * fact[n-1-i] % MOD) % MOD;
            add(perm[i]);
        }
        return (idx + 1) % MOD;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func findPermutationIndex(perm []int) int {
    MOD := int(1e9 + 7)
    n := len(perm)
    bit := make([]int, n+2)
    add := func(x int) { for ; x <= n; x += x & -x { bit[x]++ } }
    sum := func(x int) int { s := 0; for ; x > 0; x -= x & -x { s += bit[x] }; return s }
    fact := make([]int, n+1)
    fact[0] = 1
    for i := 1; i <= n; i++ { fact[i] = fact[i-1] * i % MOD }
    idx := 0
    for i := 0; i < n; i++ {
        cnt := perm[i] - 1 - sum(perm[i]-1)
        idx = (idx + cnt*fact[n-1-i]%MOD) % MOD
        add(perm[i])
    }
    return (idx + 1) % MOD
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int findPermutationIndex(int[] perm) {
        int MOD = 1_000_000_007, n = perm.length;
        int[] bit = new int[n+2];
        java.util.function.IntConsumer add = x -> { for (; x <= n; x += x & -x) bit[x]++; };
        java.util.function.IntUnaryOperator sum = x -> { int s = 0; for (; x > 0; x -= x & -x) s += bit[x]; return s; };
        long[] fact = new long[n+1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
        int idx = 0;
        for (int i = 0; i < n; i++) {
            int cnt = perm[i] - 1 - sum.applyAsInt(perm[i]-1);
            idx = (int)((idx + cnt * fact[n-1-i] % MOD) % MOD);
            add.accept(perm[i]);
        }
        return (idx + 1) % MOD;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun findPermutationIndex(perm: IntArray): Int {
        val MOD = 1_000_000_007
        val n = perm.size
        val bit = IntArray(n+2)
        fun add(x: Int) { var x = x; while (x <= n) { bit[x]++; x += x and -x } }
        fun sum(x: Int): Int { var x = x; var s = 0; while (x > 0) { s += bit[x]; x -= x and -x }; return s }
        val fact = LongArray(n+1) { 1L }
        for (i in 1..n) fact[i] = fact[i-1] * i % MOD
        var idx = 0L
        for (i in 0 until n) {
            val cnt = perm[i] - 1 - sum(perm[i]-1)
            idx = (idx + cnt * fact[n-1-i] % MOD) % MOD
            add(perm[i])
        }
        return ((idx + 1) % MOD).toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def findPermutationIndex(self, perm: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(perm)
        fact = [1] * (n+1)
        for i in range(1, n+1):
            fact[i] = fact[i-1] * i % MOD
        bit = [0] * (n+2)
        def add(x):
            while x <= n:
                bit[x] += 1
                x += x & -x
        def query(x):
            s = 0
            while x:
                s += bit[x]
                x -= x & -x
            return s
        idx = 0
        for i in range(n):
            cnt = perm[i] - 1 - query(perm[i]-1)
            idx = (idx + cnt * fact[n-1-i]) % MOD
            add(perm[i])
        return (idx + 1) % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn find_permutation_index(perm: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = perm.len();
        let mut fact = vec![1i64; n+1];
        for i in 1..=n { fact[i] = fact[i-1] * i as i64 % MOD; }
        let mut bit = vec![0; n+2];
        let mut add = |mut x: usize| { while x <= n { bit[x] += 1; x += x & (!x + 1); } };
        let mut sum = |mut x: usize| { let mut s = 0; while x > 0 { s += bit[x]; x -= x & (!x + 1); } s };
        let mut idx = 0i64;
        for i in 0..n {
            let cnt = perm[i] as usize - 1 - sum(perm[i] as usize - 1);
            idx = (idx + cnt as i64 * fact[n-1-i] % MOD) % MOD;
            add(perm[i] as usize);
        }
        ((idx + 1) % MOD) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    findPermutationIndex(perm: number[]): number {
        const MOD = 1e9 + 7, n = perm.length;
        const fact = Array(n+1).fill(1);
        for (let i = 1; i <= n; ++i) fact[i] = fact[i-1] * i % MOD;
        const bit = Array(n+2).fill(0);
        function add(x: number) { while (x <= n) { bit[x]++; x += x & -x; } }
        function sum(x: number) { let s = 0; while (x > 0) { s += bit[x]; x -= x & -x; } return s; }
        let idx = 0;
        for (let i = 0; i < n; ++i) {
            const cnt = perm[i] - 1 - sum(perm[i]-1);
            idx = (idx + cnt * fact[n-1-i] % MOD) % MOD;
            add(perm[i]);
        }
        return (idx + 1) % MOD;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), due to Fenwick Tree operations for each element.
  • 🧺 Space complexity: O(n), for the BIT and factorial arrays.