Time complexity NlogN Still TLE


#1

Try making smallest possible sized array in Merge function. Ref. Following code for help

`int Merge(vector& A, int l, int m, int r){
int ans=0;
vector tempMerge(A.size(),0);
int i=l;
int j=m+1;
int k=l;
while(i<=m && j<=r){
if(A[i]<=A[j]){
tempMerge[k]=A[i];
i++;
k++;
}
else{
tempMerge[k]=A[j];
j++;
k++;
ans+=(m-i+1);
}
}
while(i<=m){
tempMerge[k]=A[i];
i++;
k++;
// ans+=(m-i+1);
}
while(j<=r){
tempMerge[k]=A[j];
j++;
k++;
}
for(int x=l;x<=r;x++){
A[x]=tempMerge[x];
}
return ans;
}

void MSort(vector& A, int l,int r,int& ans){
if(l<r){
int m=l+(r-l)/2;
// int m=(l+r)/2;
MSort(A,l,m,ans);
MSort(A,m+1,r,ans);
ans+=Merge(A,l,m,r);
}

}

int Solution::countInversions(vector &A) {
int ans=0;
MSort(A,0,A.size()-1,ans);
return ans;
}
`