 # 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;
s.insert(A);
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;
}
``````

}