# share O(nK) solution using Java with some explanation !

• Here we have two arrays:
one is res[k],which denotes the number of k inverse pairs given a new element!
another is sum[k],which denotes the number of <=k inverse pairs given a new elements.
Then, we can use a for loop to iterate n-times to get final result, basically the core relation between res and sum is : res[j]=sum[j]-sum[j-i] if j-i>=0, else res[j] is simply equal to sum[j] given a new element has been considered, where i is 1<=i<=n, and j is i<=j<=k. Hope it helps!
More specifically, suppose we have calculated 1,2,3,4,5,6,7 elements' res and sum array. Then, after the next step, the 8 comes in. Now, as for every k, we will consider each of {8-k, 8-k+1,8-k+2,...8} as the last element to form k inverse pairs' array, that's why will have res[k]=sum[k]-sum[k-8] if k-8>=0, or res[k]=sum[k] if k<8.

More details:
It means that if k=4, then we will consider {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,8,7},{1,2,3,4,5,7,8,6}, {1,2,3,4,6,7,8,5} and {1,2,3,5,6,7,8,4} cases. As for every case, we need to fix the last element, and then focus on all the permutations of previous 7 elements. Since we already calculated res and sum for the previous step(I mean the step for only having 7 elements), so we can just retrieve information directly from res and sum and update their values.

``````public class Solution {
public int kInversePairs(int n, int k) {
long mod=(long)(1e9+7);

long[] res=new long[k+1];
long[] sum=new long[k+1];
res[0]=1;
Arrays.fill(sum,1);

for(int i=2;i<=n;i++){
//long[] temp=sum.clone();
for(int j=0;j<=k;j++){
if(j==0){
res[0]=1;
}else{
res[j]=(j-i)>=0 ? ((sum[j]-sum[j-i]+mod)%mod) : ((sum[j]+mod)%mod);
}
}

for(int j=1;j<=k;j++){
sum[j]=(res[j]+sum[j-1]+mod)%mod;
}
}

return (int)res[k];
}
}
``````

• we will consider each of {8-k, 8-k+1,8-k+2,...8} as the last element to form k inverse pairs' array

What do you mean by `we will consider each of {8-k, 8-k+1,8-k+2,...8} as the last element to form k inverse pairs' array`?

• It means that if k=4, then we will consider {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,8,7},{1,2,3,4,5,7,8,6}, {1,2,3,4,6,7,8,5} and {1,2,3,5,6,7,8,4} cases. As for every case, we need to fix the last element, and then focus on all the permutations of previous 7 elements. Since we already calculated res and sum for the previous step(I mean the step for only having 7 elements), so we can just retrieve information directly from res and sum and update their values.
Sorry, my description is a little confusing. Hope it helps.

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