Problem 629

(Last updated: )

Question statement:

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 consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo $10^9 + 7$.

Solution:

This was a hard 2-d dp solution. I had help from prior submissions and discussions, and so ultimately this is not my code.

Main idea:

Create a dp array where dp[i][j] tracks the number of sub-arrays of some permutation of 1,…,i with exactly j inverted pairs. Suppose we have completed i-1 moves, with each move placing a number down in the order of this perutation. In our $i^{\text{th}}$ move, we see where this $i^{\text{th}}$ element would fit.

  • If it does not induce any new inverted pairs, the contribution it would have to dp[i][j] is dp[i-1][j].
  • If it causes exactly one inverted pair, the contribution it would have to dp[i][j] is dp[i-1][j-1]
  • and so on… until
  • If it causes i-1 inverted pairs (i.e, it is smaller than everything in the permutation so far), then it would contribute dp[i-1][j-i+1]

Since all of these could simultaneously happen, the total contribution to dp[i][j] would be the sum
$$\sum_{k=0}^{i-1} \texttt{dp[i-1][j-k]}$$
Now we do a small trick to improve efficiency by realizing that
$$\texttt{dp[i][j]-dp[i][j-1] = dp[i-1][j] - dp[i-1][j-1]}$$
from which we can derive
$$\texttt{dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]}$$

Then you bang your head against the wall to figure out the edge cases.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def kInversePairs(self, n: int, k: int) -> int:
    kMod = 7+10**9
    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]) % kMod
            if j - i >= 0:
                dp[i][j] = (dp[i][j] - dp[i - 1] [j - i] + kMod) % kMod

    return dp[n][k]

Comments:

Time complexity: O(n*k)

At the time of submission, the above solution passes leetcode submission cases in 270ms, beats 59.30% of users. It uses 54.74MB of memory, beating 56.29% of users.