# K Inverse Pairs Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/k-inverse-pairs-array)
Canonical: https://scaleengineer.com/dsa/problems/k-inverse-pairs-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Works Applications](https://scaleengineer.com/companies/works-applications)
---
## Problem
For an integer array `nums`, an **inverse pair** is a pair of integers `[i, j]` where `0 <= i < j < nums.length` and `nums[i] > nums[j]`.

Given two integers n and k, return the number of different arrays consisting of numbers from `1` to `n` such that there are exactly `k` **inverse pairs**. Since the answer can be huge, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** n = 3, k = 0
**Output:** 1
**Explanation:** Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.

**Example 2:**

**Input:** n = 3, k = 1
**Output:** 2
**Explanation:** The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

**Constraints:**

* `1 <= n <= 1000`
* `0 <= k <= 1000`

# Approaches
## Brute-Force with Recursion
This approach involves generating every possible permutation of numbers from 1 to `n`. For each generated permutation, we count the number of inverse pairs. If the count matches `k`, we increment our result. This method is conceptually simple but computationally very expensive.
**Time:** O(n! * n^2) - There are `n!` permutations. For each permutation, we spend `O(n^2)` to count the inversions. · **Space:** O(n) - For the recursion stack depth and to store the current permutation.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will time out for all but the smallest values of `n` (e.g., n > 10).
### Explanation
The brute-force method explores all possible arrangements of the numbers from 1 to `n`. It uses a backtracking algorithm to generate each permutation. Once a full permutation of `n` numbers is formed, it iterates through the permutation to count the number of inverse pairs. If this count equals the target `k`, a solution is found.

**Algorithm:**
- Define a recursive function, say `generate(current_permutation, used_numbers)`.
- The base case for the recursion is when the `current_permutation` has `n` elements.
- In the base case, count the inverse pairs in the `current_permutation`. An inverse pair `(i, j)` exists if `i < j` and `permutation[i] > permutation[j]`.
- If the number of inverse pairs is exactly `k`, increment a counter.
- In the recursive step, iterate through numbers from 1 to `n`. If a number has not been used, add it to the `current_permutation` and make a recursive call.
- Backtrack by removing the number and marking it as unused to explore other possibilities.

```java
// This is a conceptual implementation and is too slow to pass.
class Solution {
    int count = 0;
    int N, K;
    public int kInversePairs(int n, int k) {
        this.N = n;
        this.K = k;
        // The maximum number of inversions for n elements is n*(n-1)/2.
        if (k > n * (n - 1) / 2) {
            return 0;
        }
        List<Integer> permutation = new ArrayList<>();
        boolean[] used = new boolean[n + 1];
        generate(permutation, used);
        return count;
    }

    private void generate(List<Integer> permutation, boolean[] used) {
        if (permutation.size() == N) {
            if (countInversions(permutation) == K) {
                count++;
            }
            return;
        }
        for (int i = 1; i <= N; i++) {
            if (!used[i]) {
                used[i] = true;
                permutation.add(i);
                generate(permutation, used);
                permutation.remove(permutation.size() - 1);
                used[i] = false;
            }
        }
    }

    private int countInversions(List<Integer> arr) {
        int inversions = 0;
        for (int i = 0; i < arr.size(); i++) {
            for (int j = i + 1; j < arr.size(); j++) {
                if (arr.get(i) > arr.get(j)) {
                    inversions++;
                }
            }
        }
        return inversions;
    }
}
```
### Algorithm
- Define a recursive function, say `generatePermutations(current_permutation, used_numbers)`.
- The base case for the recursion is when the `current_permutation` has `n` elements.
- In the base case, count the inverse pairs in the `current_permutation`. An inverse pair `(i, j)` exists if `i < j` and `permutation[i] > permutation[j]`.
- If the number of inverse pairs is exactly `k`, increment a global counter.
- In the recursive step, iterate through numbers from 1 to `n`. If a number has not been used, add it to the `current_permutation` and make a recursive call.
- Backtrack by removing the number and marking it as unused to explore other possibilities.

## Naive Dynamic Programming
This approach uses dynamic programming. We define `dp[i][j]` as the number of permutations of numbers from 1 to `i` that have exactly `j` inverse pairs. We build the solution for `n` and `k` based on solutions for smaller subproblems by considering the placement of the `i`-th number.
**Time:** O(n * k * n) - Three nested loops for `i`, `j`, and `p`. · **Space:** O(n * k) - For the 2D DP table.
**Pros:** Correctly models the problem using a DP state.; Significantly more efficient than the brute-force approach.
**Cons:** The time complexity is too high for the given constraints due to the third nested loop.
### Explanation
The core idea is to construct a permutation of `i` elements by inserting the number `i` into a permutation of `i-1` elements. When we insert the number `i` into a permutation of `[1, ..., i-1]`, it is larger than all existing elements. If we place `i` at the `p`-th position from the right (0-indexed), it creates `p` new inverse pairs. This leads to the recurrence relation: `dp[i][j] = sum_{p=0}^{i-1} dp[i-1][j-p]`. This means the number of ways to get `j` inversions with `i` elements is the sum of ways to get `j-p` inversions with `i-1` elements, for all possible new inversions `p` we can create (from 0 to `i-1`).

**Algorithm:**
- Create a 2D DP table `dp[n+1][k+1]`.
- Initialize the base case: `dp[0][0] = 1`.
- Iterate `i` from 1 to `n`.
- Iterate `j` from 0 to `k`.
- Inside, iterate `p` from 0 to `min(j, i-1)` to calculate the sum `dp[i][j] = (dp[i][j] + dp[i-1][j-p]) % MOD`.
- The final answer is `dp[n][k]`.

```java
class Solution {
    public int kInversePairs(int n, int k) {
        int MOD = 1_000_000_007;
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int p = 0; p < i && j - p >= 0; p++) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - p]) % MOD;
                }
            }
        }
        return dp[n][k];
    }
}
```
### Algorithm
- Create a 2D DP table `dp[n+1][k+1]`.
- Initialize the base case: `dp[0][0] = 1` (an empty permutation has 0 inversions).
- Iterate `i` from 1 to `n` (for permutations of size `i`).
- Iterate `j` from 0 to `k` (for the number of inversions).
- Inside, iterate `p` from 0 to `min(j, i-1)` to calculate the sum `dp[i][j] = (dp[i][j] + dp[i-1][j-p]) % MOD`.
- The final answer is `dp[n][k]`.

## Optimized Dynamic Programming
We can optimize the naive DP approach. The recurrence `dp[i][j] = sum_{p=0}^{i-1} dp[i-1][j-p]` involves a summation that can be calculated more efficiently. By observing the relationship between `dp[i][j]` and `dp[i][j-1]`, or by using a sliding window sum (prefix sums), we can derive a new recurrence that avoids the inner loop.
**Time:** O(n * k) - We have two nested loops, and each transition takes constant time. · **Space:** O(n * k) - For the 2D DP table.
**Pros:** Efficient enough to pass the given constraints.; Logically follows from the naive DP approach.
**Cons:** Uses a significant amount of memory for large `n` and `k`.
### Explanation
The original recurrence is: `dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-i+1]`. This is a sum over a window of size `i` on the previous row `dp[i-1]`. We can compute this sum efficiently in `O(1)` time for each `j` by maintaining a running sum.

The optimized recurrence relation is `dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i]`. This removes the innermost loop, reducing the time complexity.

**Algorithm:**
- Create a 2D DP table `dp[n+1][k+1]`.
- Initialize `dp[0][0] = 1`.
- Iterate `i` from 1 to `n`.
- Maintain a `prefixSum` for the previous row `dp[i-1]`.
- Iterate `j` from 0 to `k`.
- Update the `prefixSum` by adding `dp[i-1][j]` and subtracting `dp[i-1][j-i]` if `j >= i` (this is a sliding window sum).
- Set `dp[i][j]` to the current `prefixSum` (modulo `10^9 + 7`).
- The final answer is `dp[n][k]`.

```java
class Solution {
    public int kInversePairs(int n, int k) {
        int MOD = 1_000_000_007;
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            long prefixSum = 0;
            for (int j = 0; j <= k; j++) {
                prefixSum += dp[i - 1][j];
                if (j >= i) {
                    prefixSum -= dp[i - 1][j - i];
                }
                // Handle negative results from modulo
                dp[i][j] = (int)((prefixSum % MOD + MOD) % MOD);
            }
        }
        return dp[n][k];
    }
}
```
### Algorithm
- Create a 2D DP table `dp[n+1][k+1]`.
- Initialize `dp[0][0] = 1`.
- Iterate `i` from 1 to `n`.
- Maintain a `prefixSum` for the previous row `dp[i-1]`.
- Iterate `j` from 0 to `k`.
- Update the `prefixSum` by adding `dp[i-1][j]` and subtracting `dp[i-1][j-i]` if `j >= i` (sliding window sum).
- Set `dp[i][j]` to the current `prefixSum`.
- The final answer is `dp[n][k]`.

## Space-Optimized Dynamic Programming
This is the most efficient approach. It builds upon the optimized DP solution. By observing the recurrence, we can see that to compute the values for the current row `i`, we only need the values from the previous row `i-1`. This allows us to reduce the space complexity from `O(n*k)` to `O(k)` by using only a 1D array.
**Time:** O(n * k) - The time complexity remains the same as the `O(n*k)` space approach. · **Space:** O(k) - We use a 1D array of size `k+1` (and a temporary one of the same size) to store the DP states for one row.
**Pros:** Most efficient solution in terms of both time and space.; Passes all constraints with optimal memory usage.
**Cons:** The logic can be slightly harder to grasp compared to the 2D DP table version.
### Explanation
Instead of a 2D `dp` table, we use a 1D array to store the results for the previous row (`i-1`) and compute the results for the current row (`i`) into a temporary array. After each outer loop iteration, the temporary array becomes the main DP array for the next iteration. This reduces the space requirement significantly while keeping the time complexity the same.

**Algorithm:**
- Create a 1D array `dp` of size `k+1`. Initialize `dp[0] = 1`. This represents the base case.
- Iterate `i` from 1 to `n`.
- Inside this loop, create a temporary array `temp` of size `k+1`.
- Use a variable `val` to maintain the sliding window sum. Iterate `j` from 0 to `k`.
- Update `val` by adding `dp[j]` (from the previous row `i-1`) and subtracting `dp[j-i]` if `j >= i`.
- Set `temp[j]` to the new `val` (modulo `10^9 + 7`).
- After the inner loop, update `dp = temp` for the next iteration of `i`.
- The final answer is `dp[k]`.

```java
class Solution {
    public int kInversePairs(int n, int k) {
        int MOD = 1_000_000_007;
        int[] dp = new int[k + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            int[] temp = new int[k + 1];
            int val = 0;
            for (int j = 0; j <= k; j++) {
                val = (val + dp[j]) % MOD;
                if (j >= i) {
                    val = (val - dp[j - i] + MOD) % MOD;
                }
                temp[j] = val;
            }
            dp = temp;
        }
        return dp[k];
    }
}
```
### Algorithm
- Create a 1D array `dp` of size `k+1`. Initialize `dp[0] = 1`.
- Iterate `i` from 1 to `n`.
- Inside this loop, create a temporary array `temp` of size `k+1` to store the new values for row `i`.
- Use a variable `val` to maintain the sliding window sum. Iterate `j` from 0 to `k`.
- Update `val` by adding `dp[j]` (from the previous row `i-1`) and subtracting `dp[j-i]` if `j >= i`.
- Set `temp[j]` to the new `val` (modulo `10^9 + 7`).
- After the inner loop, update `dp = temp` for the next iteration of `i`.
- The final answer is `dp[k]`.

# Solutions
### Java

```java
class Solution {
public
  int kInversePairs(int n, int k) {
    final int mod = (int)1 e9 + 7;
    int[] f = new int[k + 1];
    int[] s = new int[k + 2];
    f[0] = 1;
    Arrays.fill(s, 1);
    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        f[j] = (s[j + 1] - s[Math.max(0, j - (i - 1))] + mod) % mod;
      }
      for (int j = 1; j <= k + 1; ++j) {
        s[j] = (s[j - 1] + f[j - 1]) % mod;
      }
    }
    return f[k];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int kInversePairs(int n, int k) {
    int f[k + 1];
    int s[k + 2];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    fill(s, s + k + 2, 1);
    s[0] = 0;
    const int mod = 1e9 + 7;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        f[j] = (s[j + 1] - s[max(0, j - (i - 1))] + mod) % mod;
      }
      for (int j = 1; j <= k + 1; ++j) {
        s[j] = (s[j - 1] + f[j - 1]) % mod;
      }
    }
    return f[k];
  }
};

```

### Python

```python
class Solution:
    def kInversePairs(self, n: int, k: int) -> int: mod = 10 ** 9 + 7 f = [1] + [0] * k s = [0] * (k + 2) for i in range(1, n + 1): for j in range(1, k + 1): f[j] = (s[j + 1] - s[max(0, j - (i - 1))]) % mod for j in range(1, k + 2): s[j] = (s[j - 1] + f[j - 1]) % mod return f[k]

```