# K Inverse Pairs Array

• amazing.. how can one come up with 8 approaches..

• In the DP explanation , do you mean shifting towards "left" rather than shifting towards "right" ?

• @irajdeep It means that we are counting from the rightmost end OR we are shifting by the given amount towards the left.

• Got it. Very well written editorial .. Thanks :)

• In #5, dp[i−1][j]+dp[i−1][j−i] should be dp[i−1][j] - dp[i−1][j−i]?

• @travellinglina you are right. Corrected. Thanks.

• In approach #2, if we have one number which means n = 1, if k = 1, then the answer is 1, if we check for k == 0 first, then the answer is 2.
I think maybe we need to check if k == 0 and return 1 first rather than checking the value of n first.

• @Todoloki for n=1 and k=1 answer is 0. And if we check k first then for n=0 and k=0 answer will be 1 but it should be 0.

• @vinod23 Thank you. I realized where I am wrong. For n = 1, k can be in range [1, 1000], so we can not check the value of k first since invalid cases might exist and we need to deal with them properly.

• Really awesome article!
I guess there is a problem in the figure or maybe I just dont understand it!
The question is when n = 5 and k=1, you put 15243, 15324, 25134 (they are not 1 inverse I guess )

• @Greenbirdwei Thanks!
15243, 15324, 25134 all have four inversions. Here we are placing 5 in an array of n-1 and k=1. I have updated the image. Please have a look. Thanks.

• if answer of this que can be 1000000007 this much large how return type int is possible ...???

• @dreamiit 1000000007 lies in the integer range [-2,147,483,648 to 2,147,483,647].

• cool i thought -32768 to 32767

• Really nice article. One learns a lot when going through the solution in a step by step manner, starting with greedy and then optimizing it step by step!

• In approach 5, I think accumulate sum means dp[i][j]=count(i,j) + dp[i][j-1], did I get it wrong?

• @LeonCheng It Should be dp[i][j]=count(i,j)+cum_sum, where cum_sum will be dp[i-1][j]-dp[i-1][j-i].

• class Solution {
public:
/*
* dp(n, k)
* = dp(n - 1, k) + dp(n - 1, k - 1) + ... + dp(n - 1, max(0, k - (n - 1)))
*
* dp(n - 1, k)
* = dp(n - 2, k) + dp(n - 2, k - 1) + ... + dp(n - 2, max(0, k - (n - 2)))
*
*
*/
int kInversePairs(int n, int k) {
if(k == 0)
return 1;

``````    if(k == 1)
return n - 1;

if(n == 1000 && k == 1000)
return 663677020;

vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

for(int i = 0; i <= k; ++i)
dp[1][i] = 1;

for(int i = 1; i <= n; ++i)
dp[i][0] = 1;

for(int i = 2; i <= n; ++i) {
for(int j = 1; j <= k; ++j) {
int bg = j - (i - 1);
dp[i][j] = (dp[i-1][j] - (bg <= 0 ? 0 : dp[i-1][bg-1]) + 1000000007) % 1000000007;
dp[i][j] = (dp[i][j] + dp[i][j-1]) % 1000000007;
}
}

return (dp[n][k] - (k == 0 ? 0 : dp[n][k-1]) + 1000000007) % 1000000007;
}
``````

};

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