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


  • 1

    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, fordp[i][j]anddp[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]
    

Log in to reply
 

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