Count the triplets such that A [ i ] < B [ j ] < C [ k ] | Java implementation of the approach ; Function to return the count of elements in arr [ ] which are less than the given key ; Modified binary search ; Function to return the count of elements in arr [ ] which are greater than the given key ; Modified binary search ; Function to return the count of the required triplets ; Sort all three arrays ; Iterate for all the elements of array B ; Count of elements in A [ ] which are less than the chosen element from B [ ] ; Count of elements in C [ ] which are greater than the chosen element from B [ ] ; Update the count ; Driver code
import java . util . * ; class GFG { static int countLessThan ( int arr [ ] , int n , int key ) { int l = 0 , r = n - 1 ; int index = - 1 ; while ( l <= r ) { int m = ( l + r ) / 2 ; if ( arr [ m ] < key ) { l = m + 1 ; index = m ; } else { r = m - 1 ; } } return ( index + 1 ) ; } static int countGreaterThan ( int arr [ ] , int n , int key ) { int l = 0 , r = n - 1 ; int index = - 1 ; while ( l <= r ) { int m = ( l + r ) / 2 ; if ( arr [ m ] <= key ) { l = m + 1 ; } else { r = m - 1 ; index = m ; } } if ( index == - 1 ) return 0 ; return ( n - index ) ; } static int countTriplets ( int n , int a [ ] , int b [ ] , int c [ ] ) { Arrays . sort ( a ) ; Arrays . sort ( b ) ; Arrays . sort ( c ) ; int count = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int current = b [ i ] ; int low = countLessThan ( a , n , current ) ; int high = countGreaterThan ( c , n , current ) ; count += ( low * high ) ; } return count ; } public static void main ( String args [ ] ) { int a [ ] = { 1 , 5 } ; int b [ ] = { 2 , 4 } ; int c [ ] = { 3 , 6 } ; int size = a . length ; System . out . println ( countTriplets ( size , a , b , c ) ) ; } }