text: Count the triplets such that A [ i ] < B [ j ] < C [ k ] | 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
code: def countLessThan ( arr , n , key ) : NEW_LINE INDENT l = 0 NEW_LINE r = n - 1 NEW_LINE index = - 1 NEW_LINE while ( l <= r ) : NEW_LINE INDENT m = ( l + r ) // 2 NEW_LINE if ( arr [ m ] < key ) : NEW_LINE INDENT l = m + 1 NEW_LINE index = m NEW_LINE DEDENT else : NEW_LINE INDENT r = m - 1 NEW_LINE DEDENT DEDENT return ( index + 1 ) NEW_LINE DEDENT def countGreaterThan ( arr , n , key ) : NEW_LINE INDENT l = 0 NEW_LINE r = n - 1 NEW_LINE index = - 1 NEW_LINE while ( l <= r ) : NEW_LINE INDENT m = ( l + r ) // 2 NEW_LINE if ( arr [ m ] <= key ) : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT else : NEW_LINE INDENT r = m - 1 NEW_LINE index = m NEW_LINE DEDENT DEDENT if ( index == - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return ( n - index ) NEW_LINE DEDENT def countTriplets ( n , a , b , c ) : NEW_LINE INDENT a . sort NEW_LINE b . sort ( ) NEW_LINE c . sort ( ) NEW_LINE count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT current = b [ i ] NEW_LINE a_index = - 1 NEW_LINE c_index = - 1 NEW_LINE low = countLessThan ( a , n , current ) NEW_LINE high = countGreaterThan ( c , n , current ) NEW_LINE count += ( low * high ) NEW_LINE DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 5 ] NEW_LINE b = [ 2 , 4 ] NEW_LINE c = [ 3 , 6 ] NEW_LINE size = len ( a ) NEW_LINE print ( countTriplets ( size , a , b , c ) ) NEW_LINE DEDENT