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
function binary_lower ( value , arr , n ) { var start = 0 ; var end = n - 1 ; var ans = - 1 ; var mid ; while ( start <= end ) { mid = parseInt ( ( start + end ) / 2 ) ; if ( arr [ mid ] >= value ) { end = mid - 1 ; ans = mid ; } else { start = mid + 1 ; } } return ans ; } function countTriplet ( arr , n , k ) { var count = 0 ; arr . sort ( ( a , b ) => a - b ) for ( var i = 2 ; i < n ; i ++ ) { var cur = binary_lower ( arr [ i ] - k , arr , n ) ; if ( cur <= i - 2 ) { count += parseInt ( ( ( i - cur ) * ( i - cur - 1 ) ) / 2 ) ; } } return count ; } var arr = [ 1 , 1 , 2 , 2 , 3 ] ; var k = 1 ; var n = arr . length ; document . write ( countTriplet ( arr , n , k ) ) ;