K Inverse Pairs Array


  • 0

    Click here to see the full article post


  • 0

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


  • 0
    I

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


  • 0

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


  • 0
    I

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


  • 0
    T

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


  • 0

    @travellinglina you are right. Corrected. Thanks.


  • 0
    T

    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.


  • 0

    @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.


  • 0
    T

    @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.


  • 0
    G

    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 )
    Looking forward to your reply


  • 0

    @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.


  • 0
    D

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


  • 0

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


  • 0
    D

    cool i thought -32768 to 32767


  • 0
    P

    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!


  • 0
    L

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


  • 0

    @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].


  • 0
    Y

    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;
    }
    

    };


Log in to reply
 

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