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.
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 <= 105perm is a permutation of [1, 2, ..., n].Problem Overview: You are given a permutation of numbers from 1..n. The goal is to determine its position (index) in the lexicographically sorted list of all permutations. Instead of generating all permutations, you compute how many permutations would appear before the given one.
Approach 1: Brute Force Permutation Generation (O(n! * n) time, O(n) space)
The direct approach generates every permutation of 1..n, sorts them lexicographically, and finds the index of the given permutation. Each permutation comparison takes O(n) time and there are n! permutations. This quickly becomes infeasible even for moderate values of n. The method is mainly useful for understanding the definition of permutation ranking but not practical for real inputs.
Approach 2: Factorial Number System with Ordered Set (O(n log n) time, O(n) space)
The lexicographic rank of a permutation can be computed using the factorial number system. For each position i, count how many unused numbers smaller than nums[i] remain. Each smaller choice would produce (n-i-1)! permutations before the current one. Maintaining remaining numbers inside an ordered structure such as a balanced tree or ordered set allows you to quickly count how many elements are smaller than the current value. Insertions and rank queries take O(log n) time.
Approach 3: Binary Indexed Tree (Fenwick Tree) (O(n log n) time, O(n) space)
This is the most common competitive programming solution. A Binary Indexed Tree efficiently tracks which numbers are still unused. Initialize the tree with frequency 1 for every value from 1..n. While iterating through the permutation, query the prefix sum up to nums[i] - 1 to count how many smaller numbers are still available. Multiply that count by (n-i-1)! and add it to the running rank. After processing the current value, update the tree to mark it as used. Each query and update runs in O(log n), making the entire algorithm O(n log n).
The Fenwick tree works well here because the problem repeatedly asks: “how many unused values smaller than x remain?” Prefix sum queries handle this exactly. The same idea could also be implemented using a Segment Tree or balanced BST, but BIT has smaller constant factors and simpler code.
Conceptually, the algorithm combines permutation ranking with fast frequency queries over an array-based data structure.
Recommended for interviews: The Binary Indexed Tree approach. Interviewers expect candidates to recognize that generating permutations is impossible for large n and switch to factorial-based ranking. Implementing the rank calculation with a Fenwick Tree shows strong understanding of prefix sums, order statistics, and efficient counting.
According to the problem requirements, we need to find out how many permutations are lexicographically smaller than the given permutation.
We consider how to calculate the number of permutations that are lexicographically smaller than the given permutation. There are two situations:
perm[0], there are (perm[0] - 1) times (n-1)! permutations.perm[0], we need to continue to consider the second element, and so on.We can use a binary indexed tree to maintain the number of elements that are smaller than the current element in the traversed elements. For the i-th element of the given permutation, the number of remaining elements that are smaller than it is perm[i] - 1 - tree.query(perm[i]), and the number of permutation types is (perm[i] - 1 - tree.query(perm[i])) times (n-i-1)!, which is added to the answer. Then we update the binary indexed tree and add the current element to the binary indexed tree. Continue to traverse the next element until all elements are traversed.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the permutation.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation Generation | O(n! * n) | O(n) | Only for understanding permutation order or very small n |
| Ordered Set / Balanced BST | O(n log n) | O(n) | When language provides built-in ordered sets or order-statistic trees |
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) | Best practical solution for fast prefix counts and competitive programming |
| Segment Tree | O(n log n) | O(n) | Useful when you already have a segment tree template or need flexible range queries |
3109. Find the Index of Permutation (Leetcode Medium) • Programming Live with Larry • 280 views views
Practice Find the Index of Permutation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor