Watch the video solution for Find the Index of Permutation, a medium level problem involving Array, Binary Search, Divide and Conquer. This walkthrough by Programming Live with Larry has 280 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |