Leetcode hard question…
can anyone please tell me why my code is not working or where i am wrong
public class Solution
{
static int num=0;
public static int reversePairs(ArrayList<Integer> arr)
{
// num=0;
int[] A=new int[arr.size()];
for(int i=0;i<arr.size();i++)
A[i]=arr.get(i);
merge(A,0,A.length-1);
// for(int i=0;i<arr.size();i++)
// System.out.println(A[i]+", ");
return num;
}
public static void merge(int[] arr, int start, int end){
if(start>=end)return;
int mid=start+(end-start)/2;
int s=start;
int m=mid+1;
int k=mid+1;
int a=0;
int[] arr2=new int[end-start+1];
merge(arr, s, mid);
merge(arr,mid+1,end);
int last=0;
while(s<=mid&&m<=end){
last=arr[m];
if(arr[s]>arr[m]){
if(arr[s]>2*arr[m])num++;
arr2[a++]=arr[m++];
}
else arr2[a++]=arr[s++];
}
while(s<=mid){
//if(arr[s]>2*last)num+=
arr2[a++]=arr[s++];
}
while(m<=end)arr2[a++]=arr[m++];
//System.out.println(" ");
for(int i=0,j=start;i<a;i++,j++){
arr[j]=arr2[i];
//System.out.print(arr[j]+" ");
}
while(k<=end){
int target=2*arr[k]+1;
//System.out.print("tar: "+target+"... ");
int l =bst(arr,start,mid,target);
if(l!=-1) {num+=mid-l+1;
System.out.print("pos: "+l+"/ ");
}
k++;
}
}
public static int bst(int[] arr, int start, int end, int target){
if(start>end)return -1;
int mid=start+(end-start)/2;
if(arr[mid]==target){
if(mid==start)return mid;
if(arr[mid-1]==target)return bst(arr,start,mid-1,target);
else return mid;
}
else if(arr[mid]>target){
if(mid==start)return mid;
if(arr[mid-1]>=target)return bst(arr,start,mid-1,target);
if(arr[mid-1]<target)return mid;
}
else{
if(mid==end)return -1;
if(arr[mid+1]>=target)return mid+1;
if(arr[mid+1]<target)return bst(arr,mid+1,end,target);
}
return -1;
}
}
i did dry run but still not getting AC