LeetCode 3193 - Count the Number of Inversions

The problem asks us to count how many permutations of the numbers [0, 1, 2, ..., n - 1] satisfy a collection of inversion constraints on prefixes.

leetcodehardarraydynamic-programming

LeetCode Problem 3193

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

LeetCode 3193 - Count the Number of Inversions

Problem Understanding

The problem asks us to count how many permutations of the numbers [0, 1, 2, ..., n - 1] satisfy a collection of inversion constraints on prefixes.

An inversion in an array is a pair of indices (i, j) such that:

  • i < j
  • nums[i] > nums[j]

For example, in the array [2, 0, 1], the pairs (0,1) and (0,2) are inversions because 2 > 0 and 2 > 1.

Each requirement is given as:

[endi, cnti]

This means:

  • Consider the prefix perm[0..endi]
  • That prefix must contain exactly cnti inversions

We must count all permutations that satisfy every requirement simultaneously.

The answer can become extremely large, so we return it modulo:

10^9 + 7

The constraints are important:

  • n <= 300
  • inversion count constraints are at most 400

A permutation of length 300 has 300! possible arrangements, which is astronomically large. This immediately tells us that brute force enumeration is impossible.

Another important observation is that inversion counts are relatively small, capped at 400. This strongly hints that a dynamic programming solution over inversion counts is intended.

The input guarantees:

  • At least one requirement exists for endi == n - 1
  • All endi values are unique

This means the final full permutation always has a required inversion count, and we never have conflicting duplicate constraints for the same prefix.

There are several important edge cases:

  • A prefix may require more inversions than mathematically possible
  • Requirements may become inconsistent with each other
  • Some prefixes may have no constraints at all
  • The inversion count may stay the same between consecutive prefixes
  • The inversion count may increase too quickly to be achievable

A correct solution must handle all these situations efficiently.

Approaches

Brute Force Approach

The most direct approach is to generate every permutation of [0, 1, ..., n - 1].

For each permutation:

  1. Compute inversion counts for all prefixes
  2. Check whether every requirement is satisfied
  3. Count valid permutations

This works because it explicitly tests every possible candidate.

However, the complexity is completely infeasible.

There are n! permutations. Even for n = 15, this becomes too large. Here n can be 300, making brute force impossible.

Key Insight

The crucial observation is that inversion counts evolve in a very structured way when building permutations incrementally.

Suppose we already built a permutation of length i with k inversions.

When inserting the next largest number into the permutation, we can place it in any position among the i + 1 slots.

If we place it:

  • at the end, we add 0 new inversions
  • one position earlier, we add 1
  • two positions earlier, we add 2
  • ...
  • at the beginning, we add i

Therefore, when extending a permutation of length i:

new_inversions = old_inversions + added

where:

0 <= added <= i

This creates a classic dynamic programming transition.

We define:

dp[length][inv]

as the number of permutations of size length having exactly inv inversions.

Then we apply prefix constraints during DP construction.

Since the maximum required inversion count is only 400, the DP remains manageable.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n²) O(n) Enumerates all permutations and checks inversions
Optimal Dynamic Programming O(n × maxInv²) O(maxInv) Builds permutations incrementally using inversion transitions

Algorithm Walkthrough

Step 1: Store Prefix Requirements

We first create an array:

required[end] = required inversion count

If a prefix has no constraint, we store -1.

For example:

requirements = [[2,2],[0,0]]

becomes:

required = [0, -1, 2]

This allows constant time checking during DP transitions.

Step 2: Validate Impossible Constraints Early

For a prefix of length L = end + 1, the maximum possible inversions are:

$\frac{L(L-1)}{2}$

If a requirement exceeds this value, the answer is immediately 0.

For example:

  • length 3
  • maximum inversions 3

So requiring 5 inversions is impossible.

Step 3: Define the DP State

We define:

dp[inv]

as the number of ways to build the current length prefix with exactly inv inversions.

Initially:

dp[0] = 1

because an empty permutation has zero inversions.

Step 4: Extend the Permutation One Number at a Time

Suppose we are building permutations of size length.

We insert the new largest number.

If the previous permutation had oldInv inversions, then inserting the new number can add:

0 to length-1

new inversions.

So:

newDp[newInv] += dp[oldInv]

where:

newInv = oldInv + added

Step 5: Apply Requirement Filtering

After computing all states for a prefix, we check whether this prefix has a required inversion count.

If it does, we discard every DP state except the required one.

This is the key optimization.

Instead of carrying unnecessary states forward, we immediately prune invalid prefixes.

Step 6: Continue Until Length n

We repeat the process until we build permutations of size n.

Since the input guarantees a requirement for n - 1, the final answer is simply:

dp[required[n-1]]

Why it works

The DP works because every permutation can be uniquely constructed by inserting the next largest element into a smaller permutation.

Each insertion contributes a predictable number of new inversions.

The DP enumerates all valid inversion totals reachable at every prefix length. Applying constraints immediately ensures only prefixes satisfying all requirements survive.

Thus every counted DP state corresponds to exactly one valid partial permutation, and every valid permutation is counted exactly once.

Python Solution

from typing import List

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        MOD = 10**9 + 7
        MAX_INV = 400

        required = [-1] * n

        for end, cnt in requirements:
            required[end] = cnt

        # Validate impossible constraints
        for end, cnt in requirements:
            length = end + 1
            max_possible = length * (length - 1) // 2

            if cnt > max_possible:
                return 0

        dp = [0] * (MAX_INV + 1)
        dp[0] = 1

        for length in range(1, n + 1):
            new_dp = [0] * (MAX_INV + 1)

            for old_inv in range(MAX_INV + 1):
                if dp[old_inv] == 0:
                    continue

                for added in range(length):
                    new_inv = old_inv + added

                    if new_inv > MAX_INV:
                        break

                    new_dp[new_inv] = (
                        new_dp[new_inv] + dp[old_inv]
                    ) % MOD

            req = required[length - 1]

            if req != -1:
                filtered = [0] * (MAX_INV + 1)

                if new_dp[req] > 0:
                    filtered[req] = new_dp[req]

                new_dp = filtered

            dp = new_dp

        final_req = required[n - 1]
        return dp[final_req]

The implementation follows the algorithm directly.

We first map each prefix index to its required inversion count. Prefixes without constraints store -1.

The validation step checks whether any requirement exceeds the theoretical maximum inversion count for that prefix length.

The DP array stores counts indexed by inversion total. Initially only zero inversions are possible.

For each new length, we create a fresh DP array and simulate inserting the next largest number into every possible position. Each insertion contributes a different number of additional inversions.

After generating all transitions for the current length, we enforce the requirement for that prefix. Every state except the required inversion count is discarded.

At the end, the DP value corresponding to the required inversion count for the full permutation is returned.

Go Solution

package main

func numberOfPermutations(n int, requirements [][]int) int {
	const MOD int = 1_000_000_007
	const MAX_INV int = 400

	required := make([]int, n)

	for i := 0; i < n; i++ {
		required[i] = -1
	}

	for _, req := range requirements {
		end := req[0]
		cnt := req[1]
		required[end] = cnt
	}

	// Validate impossible constraints
	for _, req := range requirements {
		end := req[0]
		cnt := req[1]

		length := end + 1
		maxPossible := length * (length - 1) / 2

		if cnt > maxPossible {
			return 0
		}
	}

	dp := make([]int, MAX_INV+1)
	dp[0] = 1

	for length := 1; length <= n; length++ {
		newDP := make([]int, MAX_INV+1)

		for oldInv := 0; oldInv <= MAX_INV; oldInv++ {
			if dp[oldInv] == 0 {
				continue
			}

			for added := 0; added < length; added++ {
				newInv := oldInv + added

				if newInv > MAX_INV {
					break
				}

				newDP[newInv] =
					(newDP[newInv] + dp[oldInv]) % MOD
			}
		}

		req := required[length-1]

		if req != -1 {
			filtered := make([]int, MAX_INV+1)

			if newDP[req] > 0 {
				filtered[req] = newDP[req]
			}

			newDP = filtered
		}

		dp = newDP
	}

	finalReq := required[n-1]
	return dp[finalReq]
}

The Go implementation mirrors the Python version closely.

Slices are used instead of Python lists. Since Go does not support negative indexing or dynamic resizing in the same way as Python, we explicitly allocate arrays of size MAX_INV + 1.

Modulo arithmetic uses integer operations safely because values remain within 32 bit signed range after each modulo reduction.

The filtering step creates a new slice containing only the required inversion state, matching the pruning logic from the Python solution.

Worked Examples

Example 1

n = 3
requirements = [[2,2],[0,0]]

Required array:

[0, -1, 2]

Length = 1

Start:

dp = [1,0,0,...]

Only one permutation:

[0]

with 0 inversions.

Requirement:

prefix 0 -> 0 inversions

Still valid.

Inversions Count
0 1

Length = 2

Insert new largest number 1.

From inversion count 0:

  • add 0 inversions -> [0,1]
  • add 1 inversion -> [1,0]
Inversions Count
0 1
1 1

No requirement for this prefix.

Length = 3

Insert new largest number 2.

From inversion count 0:

  • add 0 -> 0
  • add 1 -> 1
  • add 2 -> 2

From inversion count 1:

  • add 0 -> 1
  • add 1 -> 2
  • add 2 -> 3

Totals:

Inversions Count
0 1
1 2
2 2
3 1

Requirement:

exactly 2 inversions

Keep only:

Inversions Count
2 2

Answer:

2

Example 2

n = 3
requirements = [[2,2],[1,1],[0,0]]

Required array:

[0,1,2]

Length = 1

Only inversion count 0 survives.

Length = 2

Only inversion count 1 survives.

This corresponds to:

[1,0]

Length = 3

Insert 2.

Possible new inversion counts:

  • 1
  • 2
  • 3

Requirement says exactly 2.

Only one valid permutation remains:

[2,0,1]

Answer:

1

Example 3

n = 2
requirements = [[0,0],[1,0]]

Required array:

[0,0]

Length = 1

Only inversion count 0.

Length = 2

Possible inversion counts:

  • 0 -> [0,1]
  • 1 -> [1,0]

Requirement says exactly 0.

Keep only [0,1].

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n × MAX_INV × n) For each length, we try all inversion states and all insertion positions
Space O(MAX_INV) Only two DP arrays are stored

Since:

MAX_INV <= 400
n <= 300

the worst case is roughly:

300 × 400 × 300 = 36,000,000

operations, which is acceptable in optimized implementations.

The space complexity remains small because we only keep the current and next DP rows.

Test Cases

from typing import List

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        MOD = 10**9 + 7
        MAX_INV = 400

        required = [-1] * n

        for end, cnt in requirements:
            required[end] = cnt

        for end, cnt in requirements:
            length = end + 1
            max_possible = length * (length - 1) // 2

            if cnt > max_possible:
                return 0

        dp = [0] * (MAX_INV + 1)
        dp[0] = 1

        for length in range(1, n + 1):
            new_dp = [0] * (MAX_INV + 1)

            for old_inv in range(MAX_INV + 1):
                if dp[old_inv] == 0:
                    continue

                for added in range(length):
                    new_inv = old_inv + added

                    if new_inv > MAX_INV:
                        break

                    new_dp[new_inv] = (
                        new_dp[new_inv] + dp[old_inv]
                    ) % MOD

            req = required[length - 1]

            if req != -1:
                filtered = [0] * (MAX_INV + 1)

                if new_dp[req] > 0:
                    filtered[req] = new_dp[req]

                new_dp = filtered

            dp = new_dp

        return dp[required[n - 1]]

sol = Solution()

assert sol.numberOfPermutations(3, [[2,2],[0,0]]) == 2  # Example 1
assert sol.numberOfPermutations(3, [[2,2],[1,1],[0,0]]) == 1  # Example 2
assert sol.numberOfPermutations(2, [[0,0],[1,0]]) == 1  # Example 3

assert sol.numberOfPermutations(2, [[1,1]]) == 1  # Only [1,0]
assert sol.numberOfPermutations(2, [[1,0]]) == 1  # Only [0,1]

assert sol.numberOfPermutations(3, [[2,0]]) == 1  # Strictly increasing
assert sol.numberOfPermutations(3, [[2,3]]) == 1  # Strictly decreasing

assert sol.numberOfPermutations(3, [[1,1],[2,0]]) == 0  # Conflicting constraints

assert sol.numberOfPermutations(4, [[3,6]]) == 1  # Maximum inversions
assert sol.numberOfPermutations(4, [[3,0]]) == 1  # Minimum inversions

assert sol.numberOfPermutations(4, [[0,0],[1,1],[2,2],[3,3]]) == 1  # Fully constrained

assert sol.numberOfPermutations(5, [[4,11]]) == 0  # Impossible inversion count
Test Why
Example 1 Validates multiple valid permutations
Example 2 Validates fully constrained prefixes
Example 3 Validates zero inversion requirements
[[1,1]] Tests maximum inversions for size 2
[[1,0]] Tests minimum inversions for size 2
[[2,0]] Tests strictly increasing permutation
[[2,3]] Tests strictly decreasing permutation
[[1,1],[2,0]] Tests conflicting constraints
[[3,6]] Tests maximum inversions for size 4
[[3,0]] Tests minimum inversions for size 4
Fully constrained prefixes Tests repeated filtering correctness
Impossible inversion count Tests early rejection

Edge Cases

One important edge case occurs when a required inversion count exceeds the mathematical maximum possible for that prefix length. For example, a prefix of length 3 can have at most 3 inversions. Requiring 5 inversions is impossible. The implementation explicitly checks this before running DP and immediately returns 0.

Another tricky case occurs when multiple requirements are logically inconsistent. For example:

[1,1]
[2,0]

The first requirement forces the first two elements into decreasing order, but the second requires the full length three prefix to have zero inversions overall, which is impossible. The DP naturally handles this because all states eventually get filtered out.

A third important edge case involves prefixes without constraints. These prefixes must allow every possible inversion count to continue forward. The implementation handles this by skipping the filtering step whenever the requirement is -1.

A fourth subtle case occurs when inversion counts remain unchanged between consecutive prefixes. This means the newly inserted largest number must be placed at the end, adding zero inversions. The transition logic correctly supports this because insertion positions contributing 0 new inversions are always included.

Finally, the full permutation always has a requirement because the problem guarantees a constraint for n - 1. This ensures the final answer is always well defined and avoids ambiguity about which DP states should be summed at the end.