Count the Number of Inversions - Video Solutions

Problem Overview: You are given constraints about inversion counts in permutations. An inversion is a pair (i, j) where i < j and nums[i] > nums[j]. The task is to count how many valid permutations satisfy the required inversion conditions.

Approach 1: Brute Force Permutation Enumeration (O(n! * n), O(n))

Generate every permutation of the numbers 1..n. For each permutation, iterate through all index pairs and count inversions. After computing the inversion count, verify whether it satisfies the required condition. This approach is straightforward but infeasible beyond very small n because generating permutations costs O(n!) time. It mainly helps build intuition about how inversion counts behave in permutations.

Approach 2: Dynamic Programming on Permutation Size (O(n * k), O(n * k))

The key insight: when inserting the next largest number into a permutation, you control how many new inversions it creates. Define dp[i][j] as the number of permutations of length i that contain exactly j inversions. When placing the element i, it can be inserted in any of the i positions. Inserting it near the front adds more inversions, while inserting near the end adds fewer. The transition becomes dp[i][j] = sum(dp[i-1][j-x]) for all valid x positions where 0 ≤ x < i. This builds permutations incrementally while tracking inversion counts.

To make this efficient, compute transitions using prefix sums so each state can be calculated in constant time instead of iterating through all insertion positions. This reduces the complexity from O(n * k * n) to O(n * k). The DP table effectively enumerates all possible ways to distribute inversions across permutation sizes.

The constraints in the problem restrict which inversion counts are allowed for specific prefixes. While filling the DP table, you simply zero out states that violate those constraints. This filtering ensures that only permutations meeting all requirements remain counted.

This solution combines classic permutation inversion DP with constraint filtering. The reasoning heavily relies on understanding how inversions change when inserting elements into a sequence. Problems involving permutation structure and inversion counts often fall under Dynamic Programming combined with careful reasoning on Array positions and prefix properties.

Recommended for interviews: The dynamic programming approach with prefix-sum optimization is the expected solution. Brute force permutation generation demonstrates understanding of inversion definitions, but the DP formulation shows algorithmic maturity and the ability to optimize combinatorial counting problems.