Triplets in array with absolute difference less than k | Return the lower bound i . e smallest index of element having value greater or equal to value ; Return the number of triplet indices satisfies the three constraints ; sort the array ; for each element from index 2 to n - 1. ; finding the lower bound of arr [ i ] - k . ; If there are at least two elements between lower bound and current element . ; increment the count by lb - i C 2. ; Driver code
def binary_lower ( value , arr , n ) : NEW_LINE INDENT start = 0 NEW_LINE end = n - 1 NEW_LINE ans = - 1 NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE if ( arr [ mid ] >= value ) : NEW_LINE INDENT end = mid - 1 NEW_LINE ans = mid NEW_LINE DEDENT else : NEW_LINE INDENT start = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def countTriplet ( arr , n , k ) : NEW_LINE INDENT count = 0 NEW_LINE arr . sort ( ) NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT cur = ( binary_lower ( arr [ i ] - k , arr , n ) ) NEW_LINE if ( cur <= i - 2 ) : NEW_LINE INDENT count += ( ( i - cur ) * ( i - cur - 1 ) ) // 2 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 1 , 2 , 2 , 3 ] NEW_LINE k = 1 NEW_LINE n = len ( arr ) NEW_LINE print ( countTriplet ( arr , n , k ) ) NEW_LINE DEDENT