K Inverse Pairs Array: Counting Permutations with DP

Imagine you have a shelf of numbered books from 1 to n, and you want to know how many ways you can arrange them so that exactly k pairs are out of order. A pair (i, j) is "out of order" (an inverse pair) when a larger-numbered book sits to the left of a smaller one. Given n and k, return the number of such arrangements modulo 10^9 + 7.

This is LeetCode 629: K Inverse Pairs Array. For n=4 and k=2, the answer is 5. There are exactly five permutations of [1, 2, 3, 4] that contain precisely two inverse pairs.

Why this problem matters

Counting permutations with constraints is a foundational skill in combinatorics and DP. Most DP problems ask you to find the minimum cost or maximum value. This one asks you to count the number of valid arrangements, which changes the recurrence from min/max to addition. That shift is the same one you see in problems like Unique Binary Search Trees and Combination Sum IV.

The real challenge here is efficiency. A naive DP solution runs in O(n * k * n) time because each cell sums up to n terms from the previous row. The prefix sum optimization brings that down to O(n * k), which is the key insight interviewers are looking for.

The approach

Define dp[i][j] as the number of permutations of [1..i] with exactly j inverse pairs.

When you insert element i into a permutation of [1..i-1], you choose where to place it. Placing it at the end creates 0 new inverse pairs (since i is the largest). Placing it one position earlier creates 1 new inverse pair, two positions earlier creates 2, and so on. The maximum new inversions from placing element i is i-1 (putting it at the front).

This gives the recurrence:

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][max(0, j-i+1)]

Each cell is the sum of up to i consecutive values from the previous row. Computing that sum directly takes O(i) per cell, making the total O(n^2 * k). But you can precompute a prefix sum array over the previous row to turn each cell lookup into O(1), bringing the total to O(n * k).

The space-optimized version uses a single 1D array of size k+1, rebuilding it for each value of i from 2 to n.

def kInversePairs(n, k):
    MOD = 10**9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1

    for i in range(2, n + 1):
        new_dp = [0] * (k + 1)
        prefix = [0] * (k + 2)
        for j in range(k + 1):
            prefix[j + 1] = (prefix[j] + dp[j]) % MOD
        for j in range(k + 1):
            new_dp[j] = (prefix[j + 1] - prefix[max(0, j - i + 1)]) % MOD
        dp = new_dp

    return dp[k]

Step-by-step walkthrough

Let's trace through the DP table for n=4, k=2 to see how each row builds on the previous one.

The answer is dp[4][2] = 5. Five permutations of [1, 2, 3, 4] have exactly two inverse pairs: [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 4, 3], [2, 3, 1, 4], and [3, 1, 2, 4].

Complexity analysis

The prefix sum optimization is what makes this problem tractable for the given constraints (n up to 1000, k up to 1000).

Edge cases to watch for

• k = 0: the only permutation with zero inverse pairs is the sorted array [1, 2, ..., n]. The answer is always 1.
• k too large: the maximum number of inverse pairs for n elements is n*(n-1)/2 (the fully reversed array). If k exceeds this, the answer is 0. The DP handles this naturally since those cells never get filled.
• n = 1: there is only one permutation [1], which has 0 inverse pairs. dp[1][0] = 1, and dp[1][k] = 0 for all k > 0.
• Modular arithmetic: since the answer can be astronomically large, every addition and subtraction must be taken mod 10^9 + 7. In Python, the % operator handles negative results from subtraction correctly, but in C++ or Java you would need to add MOD before taking the remainder.

The building blocks

This problem is built on the 1D DP with prefix sum optimization pattern.

• State: dp[j] = number of permutations of [1..i] with exactly j inverse pairs (where i is the current outer loop variable)
• Transition: dp[j] = prefix[j+1] - prefix[max(0, j-i+1)], where prefix is the cumulative sum of the previous row
• Base case: dp[0] = 1 (one permutation with zero inversions)

The prefix sum trick appears whenever a DP recurrence sums a sliding window of values from the previous state. You will see the same optimization in:

• Range sum queries: precompute prefix sums to answer subarray sum queries in O(1)
• Sliding window DP: problems where each cell depends on a contiguous range of previous cells
• Counting problems with bounded choices: like this one, where inserting element i gives 0 to i-1 new inversions

From understanding to recall

You now know the recurrence, the prefix sum trick, and how to fill the table row by row. But knowing the approach is different from being able to write it under time pressure. In an interview, you need to remember that element i contributes 0 to i-1 new inversions, that the sum of a sliding window is handled by prefix differences, and that the loop starts at i=2 (not i=1).

This problem combines two building blocks: DP counting and prefix sum optimization. Each block is simple on its own, but combining them requires practice. The CodeBricks system isolates these building blocks and drills them with spaced repetition so that the combination feels natural. When you have internalized the prefix sum optimization as a standalone pattern, you will recognize instantly when a DP recurrence needs it.

Related posts

• Unique Binary Search Trees - counting with DP
• Combination Sum IV - DP counting permutations
• Perfect Squares - DP optimization patterns