# 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:

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

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

```python
10**9 + 7
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `n` and `k` |
| Output | Number of permutations of `1..n` with exactly `k` inverse pairs |
| Modulo | `10^9 + 7` |
| Constraints | `1 <= n <= 1000`, `0 <= k <= 1000` |

Example function shape:

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

## Examples

Example 1:

```python
n = 3
k = 0
```

The only array with zero inverse pairs is:

```python
[1, 2, 3]
```

So the answer is:

```python
1
```

Example 2:

```python
n = 3
k = 1
```

The valid arrays are:

```python
[1, 3, 2]
[2, 1, 3]
```

So the answer is:

```python
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:

```python
dp[i][j]
```

mean:

```text
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:

```python
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:

```python
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:

```text
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:

```text
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:

```python
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:

```python
dp[i - 1][j - i]
```

So the optimized recurrence is:

```python
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:

```python
dp[i][0] = 1
```

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

```python
[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

```python
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:

```python
dp[i][j]
```

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

The initialization:

```python
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:

```python
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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * k)` | There are `n * k` DP states |
| Space | `O(n * k)` | The table stores all states |

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

## Space-Optimized Version

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

```python
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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * k)` | Same number of states |
| Space | `O(k)` | Only two rows are stored |

## Testing

```python
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:

| Test | Why |
|---|---|
| `(3, 0)` | Official zero inverse pair example |
| `(3, 1)` | Official one inverse pair example |
| `(1, 0)` | Minimum `n` |
| `(2, 0)` | Sorted array only |
| `(2, 1)` | Reversed pair |
| `(3, 2)` | Middle inverse count |
| `(3, 3)` | Maximum inverse count for `n = 3` |
| `(4, 0)` | Larger sorted case |