Find the Index of Permutation - Solution & Explanation

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.