Count pairs from two arrays with difference exceeding K | set 2 | Java program for the above approach ; Function to count pairs that satisfy the given conditions ; Stores the count of pairs ; If v1 [ ] is smaller than v2 [ ] ; Sort the array v1 [ ] ; Traverse the array v2 [ ] ; Returns the address of the first number which is >= v2 [ j ] - k ; Increase the count by all numbers less than v2 [ j ] - k ; Otherwise ; Sort the array v2 [ ] ; Traverse the array v1 [ ] ; Returns the address of the first number which is > v1 [ i ] + k ; Increase the count by all numbers greater than v1 [ i ] + k ; Return the total count of pairs ; Driver Code
import java . util . * ; class GFG { static int countPairs ( int v1 [ ] , int v2 [ ] , int n , int m , int k ) { int count = 0 ; if ( n <= m ) { Arrays . sort ( v1 ) ; for ( int j = 0 ; j < m ; j ++ ) { int index = lowerBound ( v1 , 0 , n , v2 [ j ] - k ) ; count += index ; } } else { Arrays . sort ( v2 ) ; for ( int i = 0 ; i < n ; i ++ ) { int index = upperBound ( v2 , 0 , m , v1 [ i ] + k ) ; count += m - index ; } } return count ; } static int lowerBound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } static int upperBound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( a [ middle ] > element ) high = middle ; else low = middle + 1 ; } return low ; } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 9 , 1 , 8 } ; int brr [ ] = { 10 , 12 , 7 , 4 , 2 , 3 } ; int K = 3 ; int N = arr . length ; int M = brr . length ; System . out . print ( countPairs ( arr , brr , N , M , K ) ) ; } }