Very concise dp solution, C++


  • 0

    Time complexity N*log(N), space complexity N.

    class Solution {
    public:
        int reversePairs(vector<int>& nums) {
            if (nums.size()<=0) return 0;
            vector<int> visited; visited.push_back(nums[0]);
            int dp=0;
            for (int i=1; i<nums.size(); i++) {
                long ref=long(nums[i])+nums[i];
                auto it=upper_bound(visited.begin(),visited.end(),ref);
                dp+=distance(it,visited.end());
                it=lower_bound(visited.begin(),visited.end(),nums[i]);
                visited.insert(it,nums[i]);
            }
            return dp;
        }
    };
    

Log in to reply
 

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