LeetCode 3109 - Find the Index of Permutation

The problem gives us a permutation perm of the integers [1, 2, ..., n]. A permutation is simply an arrangement of all numbers from 1 to n where each number appears exactly once.

leetcodemediumarraybinary-searchdivide-and-conquerbinary-indexed-treesegment-treemerge-sortordered-set

LeetCode Problem 3109

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Solution

Problem Understanding

The problem gives us a permutation perm of the integers [1, 2, ..., n]. A permutation is simply an arrangement of all numbers from 1 to n where each number appears exactly once.

We are asked to determine the lexicographic index of this permutation among all permutations of [1, 2, ..., n] after sorting them in lexicographic order.

Lexicographic order works the same way as dictionary order. For example, for n = 3, the permutations appear in this order:

[1,2,3]

[1,3,2]

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

The permutation [3,1,2] appears at index 4, using zero-based indexing.

The constraints are important:

  • n can be as large as 100000
  • The result must be returned modulo 10^9 + 7

These constraints immediately rule out generating all permutations, because the number of permutations is n!, which becomes astronomically large even for moderate values of n.

The input is guaranteed to already be a valid permutation, so we do not need to validate duplicates or missing numbers.

Important edge cases include:

  • n = 1, where the only permutation has index 0
  • Already smallest permutation, such as [1,2,3,4]
  • Largest permutation, such as [4,3,2,1]
  • Large n, where efficiency becomes critical
  • Situations where many smaller unused numbers remain before the current number

Approaches

Brute Force Approach

The brute force solution would generate every permutation of [1,2,...,n], sort them lexicographically, and then locate the target permutation.

This works because lexicographic ordering is explicitly defined by the problem statement. Once all permutations are generated and sorted, the index can be directly determined.

However, this approach is completely infeasible for the given constraints. There are n! permutations. Even for n = 15, the number of permutations is already enormous. With n = 100000, generating permutations is impossible.

Key Insight for the Optimal Approach

Instead of generating permutations, we can directly compute how many permutations come before the given permutation.

At each position, we determine:

  • How many unused numbers smaller than the current number exist
  • How many permutations each such choice contributes

Suppose we are processing position i.

If there are k unused numbers smaller than perm[i], then each of those choices could occupy the current position, while the remaining n - i - 1 positions can be arranged in:

$$(n-i-1)!$$

ways.

So the contribution is:

$$k \times (n-i-1)!$$

We sum this contribution across all positions.

The remaining challenge is efficiently counting how many unused smaller numbers exist at each step. Since n is large, we need a data structure supporting:

  • Prefix sum queries
  • Point updates

A Binary Indexed Tree, also called a Fenwick Tree, provides both operations in O(log n) time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n) O(n! × n) Generates all permutations and searches for target
Optimal O(n log n) O(n) Uses factorial math and Fenwick Tree

Algorithm Walkthrough

  1. Precompute factorials modulo 10^9 + 7.

We will repeatedly need factorial values like (n-i-1)!. Computing them repeatedly would be expensive, so we precompute all factorials from 0 to n. 2. Initialize a Fenwick Tree.

Initially, every number from 1 to n is unused. We store this information in the Fenwick Tree by inserting frequency 1 for every number. 3. Process the permutation from left to right.

At each index i, we examine the current value perm[i]. 4. Count how many unused numbers are smaller.

Using the Fenwick Tree, we query how many numbers smaller than perm[i] are still available.

If the current value is x, we compute:

$$\text{smaller} = \text{query}(x-1)$$ 5. Compute contribution to lexicographic rank.

Every smaller unused number could have appeared at this position, and for each such choice, the remaining positions can be arranged freely.

Therefore:

$$\text{contribution} = \text{smaller} \times (n-i-1)!$$

Add this contribution to the answer. 6. Mark the current number as used.

Remove perm[i] from the Fenwick Tree by subtracting 1 at its position. 7. Continue until all positions are processed. 8. Return the final answer modulo 10^9 + 7.

Why it works

At every position, lexicographic ordering depends first on the earliest differing element. Any permutation using a smaller unused number at the current position must appear before the current permutation. For each such smaller choice, the remaining elements can be arranged arbitrarily. By counting these possibilities position by position, we exactly count how many permutations come before the target permutation.

Python Solution

from typing import List

MOD = 10**9 + 7

class FenwickTree:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index: int, delta: int) -> None:
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

class Solution:
    def getPermutationIndex(self, perm: List[int]) -> int:
        n = len(perm)

        factorial = [1] * (n + 1)
        for i in range(1, n + 1):
            factorial[i] = (factorial[i - 1] * i) % MOD

        fenwick = FenwickTree(n)

        for value in range(1, n + 1):
            fenwick.update(value, 1)

        answer = 0

        for i, value in enumerate(perm):
            smaller_unused = fenwick.query(value - 1)

            contribution = (
                smaller_unused * factorial[n - i - 1]
            ) % MOD

            answer = (answer + contribution) % MOD

            fenwick.update(value, -1)

        return answer

The implementation begins by precomputing factorial values modulo 10^9 + 7. Since factorials grow extremely quickly, modular arithmetic is applied at every multiplication step.

The FenwickTree class supports efficient prefix sum queries and updates. The query method returns how many unused numbers exist up to a given value, while update marks numbers as used or unused.

Initially, every number from 1 to n is inserted into the tree with frequency 1, indicating that all numbers are available.

As we iterate through the permutation, we determine how many smaller unused values remain before the current value. That count directly determines how many lexicographically smaller permutations begin with a smaller prefix at the current position.

After computing the contribution, we remove the current value from the Fenwick Tree so it cannot be reused later.

The final answer is accumulated modulo 10^9 + 7.

Go Solution

package main

const MOD int = 1_000_000_007

type FenwickTree struct {
	tree []int
	size int
}

func NewFenwickTree(size int) *FenwickTree {
	return &FenwickTree{
		tree: make([]int, size+1),
		size: size,
	}
}

func (f *FenwickTree) Update(index int, delta int) {
	for index <= f.size {
		f.tree[index] += delta
		index += index & -index
	}
}

func (f *FenwickTree) Query(index int) int {
	result := 0

	for index > 0 {
		result += f.tree[index]
		index -= index & -index
	}

	return result
}

func getPermutationIndex(perm []int) int {
	n := len(perm)

	factorial := make([]int, n+1)
	factorial[0] = 1

	for i := 1; i <= n; i++ {
		factorial[i] = int((int64(factorial[i-1]) * int64(i)) % MOD)
	}

	fenwick := NewFenwickTree(n)

	for value := 1; value <= n; value++ {
		fenwick.Update(value, 1)
	}

	answer := 0

	for i, value := range perm {
		smallerUnused := fenwick.Query(value - 1)

		contribution := int(
			(int64(smallerUnused) *
				int64(factorial[n-i-1])) % MOD,
		)

		answer = (answer + contribution) % MOD

		fenwick.Update(value, -1)
	}

	return answer
}

The Go implementation follows the same logic as the Python solution, but there are a few language-specific considerations.

Go integers can overflow during multiplication, so intermediate factorial and contribution calculations are cast to int64 before applying modulo arithmetic.

Slices are used instead of dynamic lists. The Fenwick Tree is implemented as a struct with associated methods for updates and queries.

Unlike Python, Go does not provide arbitrary precision integers by default, so careful modular arithmetic is necessary throughout the implementation.

Worked Examples

Example 1

Input:

perm = [1,2]

Factorials:

Value Factorial
0 1
1 1
2 2

Initial Fenwick Tree contains:

1: available
2: available

Step-by-step

Position Current Value Smaller Unused Factorial Contribution Running Answer
0 1 0 1! = 1 0 × 1 = 0 0
1 2 0 0! = 1 0 × 1 = 0 0

Final answer:

0

Example 2

Input:

perm = [3,1,2]

Factorials:

Value Factorial
0 1
1 1
2 2
3 6

Initial unused numbers:

{1,2,3}

Position 0

Current value is 3.

Unused smaller numbers are:

1, 2

Count:

2

Contribution:

$$2 \times 2! = 2 \times 2 = 4$$

Remove 3.

Remaining unused:

{1,2}

Position 1

Current value is 1.

No smaller unused numbers exist.

Contribution:

$$0 \times 1! = 0$$

Remove 1.

Remaining unused:

{2}

Position 2

Current value is 2.

No smaller unused numbers remain.

Contribution:

$$0 \times 0! = 0$$

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Each Fenwick Tree query and update takes O(log n)
Space O(n) Factorial array and Fenwick Tree each use linear space

The algorithm processes every element exactly once. For each element, it performs one prefix sum query and one update operation on the Fenwick Tree. Both operations take O(log n) time, leading to an overall complexity of O(n log n).

The factorial array and Fenwick Tree both require O(n) additional memory.

Test Cases

sol = Solution()

assert sol.getPermutationIndex([1]) == 0  # single element permutation

assert sol.getPermutationIndex([1, 2]) == 0  # smallest permutation
assert sol.getPermutationIndex([2, 1]) == 1  # largest permutation for n=2

assert sol.getPermutationIndex([1, 2, 3]) == 0  # lexicographically first
assert sol.getPermutationIndex([1, 3, 2]) == 1  # second permutation
assert sol.getPermutationIndex([2, 1, 3]) == 2  # middle permutation
assert sol.getPermutationIndex([2, 3, 1]) == 3  # middle permutation
assert sol.getPermutationIndex([3, 1, 2]) == 4  # provided example
assert sol.getPermutationIndex([3, 2, 1]) == 5  # lexicographically last

assert sol.getPermutationIndex([1, 2, 3, 4]) == 0  # smallest for n=4
assert sol.getPermutationIndex([4, 3, 2, 1]) == 23  # largest for n=4

assert sol.getPermutationIndex([2, 1, 4, 3]) == 7  # mixed ordering
assert sol.getPermutationIndex([3, 4, 1, 2]) == 16  # larger contributions early

large_perm = list(range(1, 1001))
assert sol.getPermutationIndex(large_perm) == 0  # large ascending input
Test Why
[1] Smallest possible input
[1,2] Lexicographically first permutation
[2,1] Lexicographically last permutation for n=2
[1,2,3] Baseline ascending order
[3,2,1] Maximum rank for n=3
[3,1,2] Provided example
[4,3,2,1] Maximum rank for n=4
[2,1,4,3] Mixed ordering pattern
[3,4,1,2] Large contribution at early positions
Large ascending permutation Stress test for performance

Edge Cases

One important edge case is when the permutation is already the lexicographically smallest arrangement, such as [1,2,3,4]. In this situation, every position has zero smaller unused numbers before it, so every contribution becomes zero. The implementation handles this naturally because the Fenwick Tree query returns zero at each step.

Another important edge case is the lexicographically largest permutation, such as [4,3,2,1]. Here, every position contributes the maximum possible number of permutations. This tests whether the factorial logic and accumulation are implemented correctly. Since the algorithm systematically counts all smaller unused values at each position, it correctly computes the maximum index.

A third critical edge case involves very large inputs near n = 100000. Any algorithm using nested loops or repeated linear scans would time out. The Fenwick Tree guarantees that each counting operation remains logarithmic, allowing the implementation to scale efficiently even for the largest valid inputs.

A final subtle edge case occurs when only one unused number remains. At that point, the factorial term becomes 0! = 1. Forgetting to initialize factorial[0] correctly would produce incorrect answers for the final position. The implementation explicitly sets factorial[0] = 1, ensuring correctness.