Is Find the Index of Permutation easy or hard?

The problem is typically classified as Medium. The main challenge is recognizing that generating permutations is impossible and instead computing the lexicographic rank mathematically. Implementing the solution with a Fenwick Tree requires familiarity with prefix sums and logarithmic-time updates.

Find the Index of Permutation Python/Java solution

Most implementations use the same idea: maintain a Fenwick Tree storing counts of available numbers and precompute factorial values. Python, Java, C++, Go, and TypeScript implementations all follow the same steps—query how many smaller numbers remain, add the factorial contribution, then update the tree to mark the current number as used.

How to solve Find the Index of Permutation in O(n log n)?

Iterate through the permutation from left to right and compute how many smaller unused values exist before the current number. Multiply this count by (n-i-1)! to determine how many permutations would appear before the current prefix. A Fenwick Tree efficiently tracks remaining numbers and supports prefix queries in O(log n), producing an overall O(n log n) solution.

What is the best approach for Find the Index of Permutation?

The most efficient approach uses the factorial number system combined with a Binary Indexed Tree (Fenwick Tree). For each element in the permutation, count how many smaller unused numbers remain and multiply that count by the factorial of the remaining positions. Prefix sum queries in the Fenwick Tree allow this calculation in O(log n) time per step, resulting in O(n log n) overall complexity.

Is Find the Index of Permutation asked at Google/Amazon/Meta?

Permutation ranking and order-statistics problems frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. Variants often involve counting smaller elements, computing lexicographic rank, or using Fenwick Trees and Segment Trees for efficient prefix queries.

What data structure is used in Find the Index of Permutation?

The key data structure is a Binary Indexed Tree (Fenwick Tree), which supports prefix sum queries and updates in O(log n). It tracks which numbers from 1..n are still unused while processing the permutation. Alternatives include Segment Trees or ordered sets with order-statistic operations.

What is the time complexity of Find the Index of Permutation?

The optimal solution runs in O(n log n) time using a Binary Indexed Tree or Segment Tree. Each element requires one prefix sum query and one update operation, both taking O(log n). The space complexity is O(n) to maintain the tree and factorial values.

Description Hints 3 Solution Video 12:31

3109. Find the Index of Permutation

Medium37.1% acceptancePremium elsewhere, free here

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 10⁹ + 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 <= 10⁵
perm is a permutation of [1, 2, ..., n].

Topics

Hints open one at a time

Hint 1

If perm[0] is x, there are at least (x - 1) * (n - 1)! permutations before perm. (All the ones starting with numbers less than x)

Hint 2

Can you find out what happens for perm[1] onwards?

Hint 3

Think about the count of the numbers that can be in place of perm[i] and come before it.

12:31

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2]

Input

[3,1,2]

Your code is saved on this device.Solution