Count the Number of Inversions

Count the Number of Inversions

What is this problem about?

The Count the Number of Inversions interview question typically asks you to find the total number of inversions in an array. An inversion is a pair of indices $(i, j)$ such that $i < j$ and $nums[i] > nums[j]$. This is a standard measure of how "unsorted" an array is.

However, in some advanced variations, you are given a set of requirements (e.g., at index $i$, there must be exactly $k$ inversions in the prefix $[0, i]$) and asked to find how many permutations of $[0, n-1]$ satisfy these conditions.

Why is this asked in interviews?

Companies like Google and Salesforce use this to test a candidate's knowledge of dynamic programming and combinatorics. It requires a deep understanding of how the number of inversions changes when a new element is inserted into a permutation. If you insert the $i$-th element into a permutation of $i-1$ elements, you can create anywhere from 0 to $i-1$ new inversions, depending on its position.

Algorithmic pattern used

This problem is solved using Dynamic Programming.

1. Define State: dp[i][j] is the number of permutations of length i with exactly j inversions.
2. Transition: When adding the $i$-th number, you can place it in $i$ possible slots. Placing it at the end adds 0 inversions; placing it at the very front adds $i-1$ inversions.
3. dp[i][j] = sum(dp[i-1][j-k]) for $0 \le k < i$.
4. Optimization: The sum can be calculated in $O(1)$ using a sliding window or prefix sums of the previous DP row, reducing complexity from $O(N \cdot K^2)$ to $O(N \cdot K)$.
5. Requirements: If a requirement says "index $i$ must have $k$ inversions," then for that $i$, only dp[i][k] is kept, and all other dp[i][j] are set to 0.

Example explanation

$n=3$, requirements: index 2 must have 2 inversions.

1. dp[1][0] = 1.
2. dp[2][0]=1, dp[2][1]=1 (sum of dp[1] over range of 2).
3. dp[3][j]: sum of dp[2] over range of 3.
   • dp[3][2] = dp[2][2] + dp[2][1] + dp[2][0] = 0 + 1 + 1 = 2. Result = 2. (Permutations: [2, 0, 1] and [1, 2, 0]).

Common mistakes candidates make

• Complexity: Using a triple loop for DP without prefix sum optimization.
• Modulo: Forgetting to handle negative results when using prefix sum subtraction ((a - b + mod) % mod).
• Base cases: Not initializing dp[1][0] = 1.

Interview preparation tip

Master the "Insertion Method" for permutations. Understanding how the $i$-th element's position affects global properties (like inversions or peaks) is the key to solving many Hard-level combinatorics DP problems.