k | Python3 program to find k - th absolute difference between two elements ; returns number of pairs with absolute difference less than or equal to mid . ; Upper bound returns pointer to position of next higher number than a [ i ] + mid in a [ i . . n - 1 ] . We subtract ( a + i + 1 ) from this position to count ; Returns k - th absolute difference ; Sort array ; Minimum absolute difference ; Maximum absolute difference ; Do binary search for k - th absolute difference ; Driver code
from bisect import bisect as upper_bound NEW_LINE def countPairs ( a , n , mid ) : NEW_LINE INDENT res = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT res += upper_bound ( a , a [ i ] + mid ) NEW_LINE DEDENT return res NEW_LINE DEDENT def kthDiff ( a , n , k ) : NEW_LINE INDENT a = sorted ( a ) NEW_LINE low = a [ 1 ] - a [ 0 ] NEW_LINE for i in range ( 1 , n - 1 ) : NEW_LINE INDENT low = min ( low , a [ i + 1 ] - a [ i ] ) NEW_LINE DEDENT high = a [ n - 1 ] - a [ 0 ] NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = ( low + high ) >> 1 NEW_LINE if ( countPairs ( a , n , mid ) < k ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid NEW_LINE DEDENT DEDENT return low NEW_LINE DEDENT k = 3 NEW_LINE a = [ 1 , 2 , 3 , 4 ] NEW_LINE n = len ( a ) NEW_LINE print ( kthDiff ( a , n , k ) ) NEW_LINE