Showing MLE (memory limit exceeded)


#1

Can anyone help how it can be improved?

int Solution::countInversions(vector<int> &arr) {
    int sum=0;
    vector<vector<int>> dp; vector<int> temp;
    for(int i=0; i<arr.size(); i++)
        dp.push_back(temp);

    for(int i=arr.size()-1; i>=0; i--){
        for(int j=i+1; j<arr.size(); j++){
            if( arr[i] > arr[j]){ // can add 1 more case
                dp[i].push_back(arr[j]);
            }
            else if( arr[i] < arr[j] ){
                for(int k=0; k<dp[j].size(); k++ ){
                    if( arr[i] > dp[j][k] )
                        dp[i].push_back( dp[j][k] );
                }
                break;
            }
        }
    }
    for(int i=0; i<dp.size(); i++)
        sum += dp[i].size();
    return sum;
}

dp[i] is a vector, storing values of possible pair
memory – O(n^2) – descending order, time – O(n^2) – descending order


#2

Expected time complexity would be O(n log n).
It requires a modification to merge sort.