LeetCode 629: K Inverse Pairs Array

Problem Restatement

We are given two integers n and k.

We need to count how many different arrays can be formed using the numbers from 1 to n exactly once, such that the array has exactly k inverse pairs.

An inverse pair is a pair of indices (i, j) where:

i < j and nums[i] > nums[j]

Because the answer can be very large, return it modulo:

10**9 + 7

Input and Output

Example function shape:

def kInversePairs(n: int, k: int) -> int:
    ...

Examples

Example 1:

n = 3
k = 0

The only array with zero inverse pairs is:

[1, 2, 3]

So the answer is:

1

Example 2:

n = 3
k = 1

The valid arrays are:

[1, 3, 2]
[2, 1, 3]

So the answer is:

2

First Thought: Generate All Permutations

A direct solution is to generate every permutation of 1..n, count inverse pairs for each permutation, and count the ones with exactly k inverse pairs.

This is far too slow.

There are n! permutations, and counting inverse pairs for each one can take O(n^2) time.

For n <= 1000, this approach is impossible.

We need dynamic programming.

Key Insight

Let:

dp[i][j]

mean:

the number of permutations of numbers 1..i with exactly j inverse pairs

Now suppose we already know all answers for 1..i-1.

We insert the largest number i into a permutation of 1..i-1.

Since i is the largest number, it creates inverse pairs only with numbers after it.

If we insert i at the end, it creates 0 new inverse pairs.

If we insert i one position before the end, it creates 1 new inverse pair.

If we insert i at the front, it creates i - 1 new inverse pairs.

So inserting i can add any number of new inverse pairs from 0 to i - 1.

Therefore:

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + ... + dp[i - 1][j - (i - 1)]

We only include terms where the index is non-negative.

Slow DP Recurrence

The direct recurrence is:

dp[i][j] = sum(dp[i - 1][j - x] for x in range(i) if j - x >= 0)

Here, x is the number of new inverse pairs created by inserting i.

This is correct, but it takes O(n * k * n) time, because each state sums up to i previous states.

With n and k up to 1000, we want O(n * k).

Prefix Sum Optimization

For fixed i, each dp[i][j] is a window sum over the previous row:

dp[i - 1][j] + dp[i - 1][j - 1] + ... + dp[i - 1][j - i + 1]

The next value dp[i][j - 1] is almost the same window:

dp[i - 1][j - 1] + dp[i - 1][j - 2] + ... + dp[i - 1][j - i]

So we can compute each new value from the previous one:

dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

But if the window becomes too large, we must remove the value that falls out:

dp[i - 1][j - i]

So the optimized recurrence is:

dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

if j >= i:
    dp[i][j] -= dp[i - 1][j - i]

All operations are done modulo 10^9 + 7.

Algorithm

Create a DP table with n + 1 rows and k + 1 columns.

Initialize:

dp[i][0] = 1

For every i, there is exactly one permutation with zero inverse pairs:

[1, 2, 3, ..., i]

Then fill the table:

1. Iterate i from 1 to n.
2. Iterate j from 1 to k.
3. Set dp[i][j] using the prefix-sum recurrence.
4. Return dp[n][k].

Implementation

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7

        dp = [[0] * (k + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            dp[i][0] = 1

        for i in range(1, n + 1):
            for j in range(1, k + 1):
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD

                if j >= i:
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i]) % MOD

        return dp[n][k]

Code Explanation

The table entry:

dp[i][j]

stores the number of permutations of 1..i with exactly j inverse pairs.

The initialization:

for i in range(n + 1):
    dp[i][0] = 1

handles the case where we want zero inverse pairs.

There is only one sorted permutation for each i.

The main recurrence is:

dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD

This extends the previous window sum by adding dp[i - 1][j].

If the window has more than i terms, we remove the extra old term:

if j >= i:
    dp[i][j] = (dp[i][j] - dp[i - 1][j - i]) % MOD

The modulo keeps the value in range.

In Python, using % MOD after subtraction also prevents negative values.

Correctness

We prove that dp[i][j] stores the number of permutations of 1..i with exactly j inverse pairs.

For j = 0, there is exactly one such permutation: the sorted increasing order. So dp[i][0] = 1 is correct.

Now assume the values for i - 1 are correct.

Take any permutation of 1..i. Remove the largest number i. The remaining array is a permutation of 1..i-1.

When we insert i back into that smaller permutation, it creates one inverse pair with each element placed after it. Since there are i - 1 other elements, inserting i can create any value from 0 to i - 1 new inverse pairs.

Therefore, to form a permutation of 1..i with exactly j inverse pairs, we may start from a permutation of 1..i-1 with j - x inverse pairs, where x is between 0 and i - 1.

So:

dp[i][j] = sum(dp[i - 1][j - x] for x in range(i) if j - x >= 0)

The prefix-sum recurrence computes exactly this same sum, only faster, by reusing the previous window sum.

Thus every valid permutation is counted once, and no invalid permutation is counted. Therefore, the algorithm returns the correct answer.

Complexity

This fits the constraints n <= 1000 and k <= 1000.

Space-Optimized Version

We only need the previous row to compute the current row.

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7

        prev = [0] * (k + 1)
        prev[0] = 1

        for i in range(1, n + 1):
            curr = [0] * (k + 1)
            curr[0] = 1

            for j in range(1, k + 1):
                curr[j] = (curr[j - 1] + prev[j]) % MOD

                if j >= i:
                    curr[j] = (curr[j] - prev[j - i]) % MOD

            prev = curr

        return prev[k]

This version uses O(k) space.

Testing

def run_tests():
    s = Solution()

    assert s.kInversePairs(3, 0) == 1
    assert s.kInversePairs(3, 1) == 2
    assert s.kInversePairs(1, 0) == 1
    assert s.kInversePairs(2, 0) == 1
    assert s.kInversePairs(2, 1) == 1
    assert s.kInversePairs(3, 2) == 2
    assert s.kInversePairs(3, 3) == 1
    assert s.kInversePairs(4, 0) == 1

    print("all tests passed")

run_tests()

Test meaning: