Kth smallest element in the array using constant space when array can 't be modified | Function to return the kth smallest element from the array ; Minimum and maximum element from the array ; Modified binary search ; To store the count of elements from the array which are less than mid and the elements which are equal to mid ; If mid is the kth smallest ; If the required element is less than mid ; If the required element is greater than mid ; Driver code
function kthSmallest ( arr , k , n ) { let temp = [ ... arr ] ; let low = temp . sort ( ( a , b ) => a - b ) [ 0 ] ; let high = temp [ temp . length - 1 ] ; while ( low <= high ) { let mid = low + Math . floor ( ( high - low ) / 2 ) ; let countless = 0 , countequal = 0 ; for ( let i = 0 ; i < n ; ++ i ) { if ( arr [ i ] < mid ) ++ countless ; else if ( arr [ i ] == mid ) ++ countequal ; } if ( countless < k && ( countless + countequal ) >= k ) { return mid ; } else if ( countless >= k ) { high = mid - 1 ; } else if ( countless < k && countless + countequal < k ) { low = mid + 1 ; } } } let arr = [ 7 , 10 , 4 , 3 , 20 , 15 ] ; let n = arr . length ; let k = 3 ; document . write ( kthSmallest ( arr , k , n ) ) ;