unks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:T1dc2,

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:

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:

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

Initialize a Fenwick Tree (BIT) of size n to keep track of used numbers.
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.
Sum all contributions and return (index + 1) % MOD (since index is 0-based).

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int findPermutationIndex(vector<int>& perm) {\n        const int MOD = 1e9 + 7;\n        int n = perm.size();\n        vector<int> bit(n+2, 0);\n        auto add = [&](int x) { for (; x <= n; x += x & -x) bit[x] += 1; };\n        auto sum = [&](int x) { int s = 0; for (; x; x -= x & -x) s += bit[x]; return s; };\n        vector<long long> fact(n+1, 1);\n        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i % MOD;\n        int idx = 0;\n        for (int i = 0; i < n; ++i) {\n            int cnt = perm[i] - 1 - sum(perm[i] - 1);\n            idx = (idx + 1LL * cnt * fact[n-1-i] % MOD) % MOD;\n            add(perm[i]);\n        }\n        return (idx + 1) % MOD;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func findPermutationIndex(perm []int) int {\n    MOD := int(1e9 + 7)\n    n := len(perm)\n    bit := make([]int, n+2)\n    add := func(x int) { for ; x <= n; x += x & -x { bit[x]++ } }\n    sum := func(x int) int { s := 0; for ; x > 0; x -= x & -x { s += bit[x] }; return s }\n    fact := make([]int, n+1)\n    fact[0] = 1\n    for i := 1; i <= n; i++ { fact[i] = fact[i-1] * i % MOD }\n    idx := 0\n    for i := 0; i < n; i++ {\n        cnt := perm[i] - 1 - sum(perm[i]-1)\n        idx = (idx + cnt*fact[n-1-i]%MOD) % MOD\n        add(perm[i])\n    }\n    return (idx + 1) % MOD\n}","lang":"go"},{"language":"Java","c

Related Tags