O(NlogN) solution still gets Time Limit Exceeded


#1

How can I make this more time efficient?
At least it is a small, simple solution that gives correct answer.

int Solution::countInversions(vector<int> &A) {
    multiset<int> s;
    int max = A[0];
    s.insert(A[0]);
    for (int i = 1; i < len; i++) {
        int x = A[i];
        if (max > x) {
            count += distance(s.upper_bound(x), s.end());
        }
        else {
            max = x;
        }
        s.insert(x);
    }
}

#2

the worst case time complexity of above implementation is O(n2) as distance function in STL takes O(n) time worst case


#3

public class Solution {
static int merger(int arr[],int temp[],int left,int mid,int right){
int inv_c=0;
int i=left;
int j=mid;
int k=left;

    while(i<=mid-1 && j<=right){
        if(arr[i]<=arr[j]) temp[k++]=arr[i++];
        else{
            temp[k++]=arr[j++];
            
            inv_c+=(mid-i);
        }
    }
    while(i<=mid-1){
        temp[k++]=arr[i++];
    }
    while(j<=right){
        temp[k++]=arr[j++];
    }
    for(int counter=left;counter<=right;counter++){
        arr[counter]=temp[counter];
    }
    return inv_c;
}
static int mergesort(int arr[],int temp[],int left,int right){
    int inversecount=0;
    int mid=0;
    if(left<right){
        mid=(left+right)/2;
        inversecount+=mergesort(arr,temp,left,mid);
        inversecount+=mergesort(arr,temp,mid+1,right);
        inversecount+=merger(arr,temp,left,mid+1,right);
    
        
    }
    return inversecount;
}
public int countInversions(int[] arr) {
    int N=arr.length;
    int temp[]=new int[N];
    int result= mergesort(arr,temp,0,N-1);
    return result;
}

}