C++ O(n*k) Solution with O(k) space


  • 0
    C
    class Solution {
    public:
        int kInversePairs(int n, int k) {
            static const int kMod = 1e9 + 7;
            // n k ?
            // 2 0 1   : 12
            // 2 1 1   : 21
            // ---------------------
            // 3 0 1   : 123
            // 3 1 2   : 132 213
            // 3 2 2   : 312 231
            // 3 3 1   : 321
            // ---------------------
            // 4 0 ?   : 1234
            // 4 1     : 1243(from 0);  1324 2134(from 1)
            // 4 2     : 1423(from 0);  1342 2143(from 1);  3124 2314(from 2)
            // 4 3     : 4123(from 0);  1432 2413(from 1);  3142 2341(from 2);  3214(from 3)
            // 4 4     : 4132 4213(from 1);  3412 2431(from 2);  3241(from 3);
            vector<int> count(k + 1, 0);
            count[0] = 1;
            int end = 0;
            for (int i = 2; i <= n; ++i) {
                vector<int> tmp(k + 1, 0);
                end = min(k, end + i - 1);
                tmp[0] = 1;
                for (int head = 1, tail = 0; head <= end; ++head) {
                    tmp[head] = (tmp[head - 1] + count[head]) % kMod;
                    if (head - tail >= i) {
                        tmp[head] -= count[tail];
                        ++tail;
                        if (tmp[head] < 0) {
                            tmp[head] += kMod;
                        }
                    }
                }
                swap(tmp, count);
            }
            return count.back();
        }
    };
    

Log in to reply
 

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