Problem Description

You are given an array perm of length n which is a permutation of [1, 2, ..., n]. Your task is to find the index (0-based) of this permutation in the lexicographically sorted list of all possible permutations of [1, 2, ..., n].

For example, if n = 3, all permutations in lexicographical order are:

• Index 0: [1, 2, 3]
• Index 1: [1, 3, 2]
• Index 2: [2, 1, 3]
• Index 3: [2, 3, 1]
• Index 4: [3, 1, 2]
• Index 5: [3, 2, 1]

The problem asks you to determine which position (index) the given permutation perm occupies in this sorted sequence.

Since the total number of permutations can be very large (n!), and consequently the index can also be very large, you need to return the result modulo 10^9 + 7.

The solution uses a Binary Indexed Tree (Fenwick Tree) to efficiently count how many permutations come before the given one. For each position i in the permutation, it calculates how many permutations would be lexicographically smaller by:

1. Counting elements that could appear at position i and are smaller than perm[i]
2. Multiplying this count by the factorial of remaining positions (n-i-1)!
3. Using the Binary Indexed Tree to track which numbers have already been used in previous positions

The sum of all these contributions gives the final index of the permutation in the lexicographically sorted list.

Intuition

To find the index of a permutation, we need to count how many permutations come before it lexicographically. Let's think about this step by step.

Consider a permutation like [3, 1, 4, 2]. How many permutations are smaller than this one?

First, any permutation starting with 1 or 2 will be smaller than one starting with 3. If we fix the first position as 1, we can arrange the remaining numbers {2, 3, 4} in any order - that's 3! ways. Similarly for starting with 2. So permutations starting with numbers less than 3 contribute 2 × 3! to our count.

Now, for permutations starting with 3, we need to look at the second position. Our permutation has 1 in the second position. Among the remaining unused numbers {1, 2, 4}, there are no numbers smaller than 1, so no additional permutations are smaller at this level.

Moving to the third position with value 4, the remaining unused numbers are {2, 4}. The number 2 is smaller than 4, so any permutation with [3, 1, 2, ...] would be smaller than [3, 1, 4, ...]. That adds 1 × 1! more permutations.

This reveals the pattern: at each position i, we count how many unused numbers are smaller than perm[i], then multiply by (n-i-1)! (the factorial of remaining positions).

The key challenge is efficiently tracking which numbers have been used and counting how many available numbers are smaller than the current one. Initially, all numbers from 1 to n are available. As we process each position, we "remove" that number from our available set.

A Binary Indexed Tree perfectly solves this tracking problem. We can:

• Query how many numbers up to x have been used: tree.query(x)
• Mark a number as used: tree.update(x, 1)
• Calculate available numbers smaller than x: (x - 1) - tree.query(x)

By summing up the contributions from each position, we get the total number of permutations that come before the given one, which is exactly the index we're looking for.

Learn more about Segment Tree, Binary Search, Divide and Conquer and Merge Sort patterns.

Solution Approach

The solution implements the counting strategy using a Binary Indexed Tree (Fenwick Tree) for efficient tracking of used numbers.

Binary Indexed Tree Setup: The BinaryIndexedTree class maintains an array c where we track which numbers have been used. The tree supports:

• update(x, delta): Marks position x with a value change of delta
• query(x): Returns the sum of all values from position 1 to x

Main Algorithm:

1. Initialize factorial array: Create an array f where f[i] = i! to store factorials from 0! to (n-1)!. This avoids recalculating factorials repeatedly.

   f = [1] * n
   for i in range(1, n):
       f[i] = f[i - 1] * i % mod

2. Process each position: For each element perm[i] at position i:

   • Calculate how many unused numbers are smaller than perm[i]:

     cnt = x - 1 - tree.query(x)

     Here, x - 1 is the total count of numbers smaller than x, and tree.query(x) tells us how many of those have already been used.

   • Add the contribution to the answer:

     ans += cnt * f[n - i - 1] % mod

     This multiplies the count of available smaller numbers by (n-i-1)!, which is the number of ways to arrange the remaining positions.

   • Mark the current number as used:

     tree.update(x, 1)

Example Walkthrough: For perm = [3, 1, 4, 2]:

• Position 0, value 3: cnt = 3 - 1 - 0 = 2 smaller unused numbers (1 and 2). Add 2 × 3! = 12
• Position 1, value 1: cnt = 1 - 1 - 0 = 0 smaller unused numbers. Add 0 × 2! = 0
• Position 2, value 4: cnt = 4 - 1 - 2 = 1 smaller unused number (2). Add 1 × 1! = 1
• Position 3, value 2: cnt = 2 - 1 - 1 = 0 smaller unused numbers. Add 0 × 0! = 0
• Total: 12 + 0 + 1 + 0 = 13

The time complexity is O(n log n) due to the Binary Indexed Tree operations, and the space complexity is O(n) for storing the tree and factorial array.

Example Walkthrough

Let's walk through finding the index of permutation [2, 3, 1] where n = 3.

Step 1: Initialize

• Create factorial array: f = [1, 1, 2] (representing 0!, 1!, 2!)
• Create Binary Indexed Tree to track used numbers
• Set ans = 0

Step 2: Process position 0 (value = 2)

• Numbers smaller than 2: {1}
• Count unused numbers smaller than 2:
  • Total smaller: 2 - 1 = 1
  • Already used: tree.query(2) = 0
  • Unused smaller: 1 - 0 = 1
• Contribution: 1 × f[3-0-1] = 1 × 2! = 2
• Update ans = 0 + 2 = 2
• Mark 2 as used: tree.update(2, 1)

Step 3: Process position 1 (value = 3)

• Numbers smaller than 3: {1, 2}
• Count unused numbers smaller than 3:
  • Total smaller: 3 - 1 = 2
  • Already used: tree.query(3) = 1 (only 2 is used)
  • Unused smaller: 2 - 1 = 1
• Contribution: 1 × f[3-1-1] = 1 × 1! = 1
• Update ans = 2 + 1 = 3
• Mark 3 as used: tree.update(3, 1)

Step 4: Process position 2 (value = 1)

• Numbers smaller than 1: none
• Count unused numbers smaller than 1:
  • Total smaller: 1 - 1 = 0
  • Already used: tree.query(1) = 0
  • Unused smaller: 0 - 0 = 0
• Contribution: 0 × f[3-2-1] = 0 × 0! = 0
• Update ans = 3 + 0 = 3
• Mark 1 as used: tree.update(1, 1)

Final Result: 3

This means [2, 3, 1] is at index 3 in the lexicographically sorted list of all permutations of [1, 2, 3].

We can verify this by listing all permutations:

• Index 0: [1, 2, 3]
• Index 1: [1, 3, 2]
• Index 2: [2, 1, 3]
• Index 3: [2, 3, 1] ✓
• Index 4: [3, 1, 2]
• Index 5: [3, 2, 1]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is determined by analyzing the main operations:

• The outer loop in getPermutationIndex runs n times, where n is the length of the permutation
• Inside each iteration:
  • tree.query(x) is called once, which has O(log n) complexity due to the while loop that runs at most log n times (it removes the least significant bit in each iteration with x -= x & -x)
  • tree.update(x, 1) is called once, which also has O(log n) complexity due to the while loop that runs at most log n times (it adds the least significant bit in each iteration with x += x & -x)
  • Other operations like modular arithmetic are O(1)
• Therefore, the total time complexity is O(n) × O(log n) = O(n × log n)

Space Complexity: O(n)

The space complexity comes from:

• The BinaryIndexedTree's array self.c of size n + 1: O(n)
• The factorial array f of size n: O(n)
• Other variables use constant space: O(1)
• Total space complexity is O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Counting of Available Numbers

Pitfall: A common mistake is incorrectly calculating how many smaller numbers are still available at each position. Developers often forget to subtract the already-used numbers or miscalculate the formula.

Incorrect approach:

# Wrong: Just counting all smaller numbers
available_smaller_count = value - 1

Correct approach:

# Right: Count smaller numbers minus those already used
used_smaller_count = fenwick_tree.query(value)
available_smaller_count = value - 1 - used_smaller_count

2. Off-by-One Errors with Tree Indexing

Pitfall: Binary Indexed Trees are typically 1-indexed, but the permutation might be 0-indexed. Mixing these indexing systems leads to incorrect results.

Incorrect approach:

# Wrong: Using 0-based indexing with BIT
tree = BinaryIndexedTree(n)  # Should be n+1 for values 1 to n
tree.update(perm[i] - 1, 1)  # Wrong adjustment

Correct approach:

# Right: BIT sized for values 1 to n
tree = BinaryIndexedTree(n + 1)
tree.update(value, 1)  # Direct use since perm contains values 1 to n

3. Integer Overflow with Factorials

Pitfall: Factorials grow extremely fast. Without proper modulo operations, intermediate calculations will overflow even with 64-bit integers.

Incorrect approach:

# Wrong: No modulo during factorial computation
factorial = [1] * n
for i in range(1, n):
    factorial[i] = factorial[i - 1] * i  # Can overflow!

# Wrong: Late modulo application
result += available_smaller_count * factorial[remaining_positions]
result %= MOD  # Too late, overflow already happened

Correct approach:

# Right: Apply modulo at each step
factorial = [1] * n
for i in range(1, n):
    factorial[i] = factorial[i - 1] * i % MOD

# Right: Modulo during multiplication
permutations_before = available_smaller_count * factorial[remaining_positions] % MOD
result = (result + permutations_before) % MOD

4. Forgetting to Mark Numbers as Used

Pitfall: After processing each position, forgetting to update the Binary Indexed Tree means the same number could be incorrectly counted as available in subsequent positions.

Incorrect approach:

for position, value in enumerate(perm):
    available_smaller_count = value - 1 - fenwick_tree.query(value)
    result += available_smaller_count * factorial[n - position - 1] % MOD
    # Forgot to mark as used!

Correct approach:

for position, value in enumerate(perm):
    available_smaller_count = value - 1 - fenwick_tree.query(value)
    result = (result + available_smaller_count * factorial[n - position - 1]) % MOD
    fenwick_tree.update(value, 1)  # Mark this number as used

5. Misunderstanding the Problem Requirements

Pitfall: Confusing whether the result should be 0-indexed or 1-indexed. The problem asks for the 0-based index, meaning the first permutation has index 0.

Incorrect approach:

# Wrong: Adding 1 for 1-based indexing
return (result + 1) % MOD

Correct approach:

# Right: Return 0-based index directly
return result