# Python O(nk) time solution from O(nk) space to O(k) space with explanation.

• #### Idea:

You can write down some the cases from 1 to 4 and you will find the pattern.
Like when `i = 4`, you insert 4 to all the cases in a proper position when `i = 3` to get the number of results when `i=4`.
Note that `i` limits the number of places you can do the insertion. If `i = 5`, there is only `5` places you can insert.
So you start from `i = 0` as base case and you can get the final result at the end.

This is what we get from the above conclusion.

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

But if you want to get your solution accepted in Python, then you need more optimization (BTW: I think is unfair since C++'s solution can pass it).
Actually, the above formula does have lots of redundant computation. As you can see, for`dp[i][j]`and`dp[i][j-1]`, we may use `dp[i-1][j-1], dp[i-1][j-2],...,dp[i-1][j-i+1]`twice. Thus, I rewrite the formula as follows.

`dp[i][j] = dp[i][j-1] + dp[i-1][j] - (if j - i >= 0: dp[i-1][j-i] else: 0)`

It works like a sliding window, adding `dp[i-1][j]`to `dp[i][j-1]` and then reducing `dp[i-1][j-i]` if applicable to remain a sliding window whose size is `i`.

O(nk) space solution

``````class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
MOD = 10**9 + 7
upper = n * (n - 1) / 2
if k == 0 or k == upper:
return 1
if k > upper:
return 0
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
dp[i][0] = 1
for j in range(k + 1):
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD
if j - i >= 0:
dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + MOD) % MOD
return dp[n][k]
``````

O(k) space solution

``````class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
MOD = 10**9 + 7
upper = n * (n - 1) / 2
if k == 0 or k == upper:
return 1
if k > upper:
return 0
dp = [0] * (k + 1)
dp[0] = 1
for i in range(1, n + 1):
temp =[1] + [0] * k
for j in range(k + 1):
temp[j] = (temp[j-1] + dp[j]) % MOD
if j - i >= 0:
temp[j] = (temp[j] - dp[j - i]) % MOD
dp = temp
return dp[k]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.