Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class ReversePairs {
public static void findPairs(int [] A){
int len = A.length-1;
//find the start index of part two sorted array
int m=0;
for (int i = 0; i <len ; i++) {
if(A[i]>A[i+1]){
m=i+1;
break;
}
}
//initialize result
int result = 0;
//part one
int start_partOne = 0;
int end_partOne = m-1;
//part two
int start_partTwo = m;
int end_partTwo = len-1;
//take two pointers, at the beginning of both parts
int i = start_partOne;
int j = start_partTwo;
while(i<=end_partOne && j<=end_partTwo){
if (A[i]<=A[j])
i++;
else if(A[i]>A[j]){
result+=end_partOne-i+1;
j++;
}
}
System.out.println("No of reversed pair: " + result);
}
public static void main(String[] args) {
int [] A = {4, 6, 8, 9, 0, 1, 2, 5, 10, 11};
findPairs(A);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment