Minimum and maximum count of elements at D distance from arr [ i ] in either direction | Function to find the minimum and maximum number of points included in a range of distance D ; Stores the minimum and maximum number of points that lies over the distance of D ; Iterate the array ; Count of elements included to left of point at index i ; Update the minimum number of points ; Update the maximum number of points ; Count of elements included to right of point at index i ; Update the minimum number of points ; Update the maximum number of points ; Return the array ; Function to perform the Binary Search to the left of arr [ i ] over the given range ; Base Case ; Binary Search for index to left ; update index ; Return the number of elements by subtracting indices ; Function to perform the Binary Search to the right of arr [ i ] over the given range ; Base Case ; Binary Search for index to right ; Update the index ; Return the number of elements by subtracting indices ; Driver Code ; Function Call
function minMaxRange ( arr , D , N ) { let max = 1 , min = N ; for ( let i = 0 ; i < N ; i ++ ) { let dist = leftSearch ( arr , arr [ i ] - D , i ) ; min = Math . min ( min , dist ) ; max = Math . max ( max , dist ) ; dist = rightSearch ( arr , arr [ i ] + D , i ) ; min = Math . min ( min , dist ) ; max = Math . max ( max , dist ) ; } return [ min , max ] ; } function leftSearch ( arr , val , i ) { if ( i == 0 ) return 1 ; let left = 0 , right = i - 1 ; let ind = - 1 ; while ( left <= right ) { let mid = Math . floor ( ( left + right ) / 2 ) ; if ( arr [ mid ] < val ) { left = mid + 1 ; } else { right = mid - 1 ; ind = mid ; } } return ind != - 1 ? i - ind + 1 : 1 ; } function rightSearch ( arr , val , i ) { if ( i == arr . length - 1 ) return 1 ; let left = i + 1 ; let right = arr . length - 1 ; let ind = - 1 ; while ( left <= right ) { let mid = Math . floor ( ( left + right ) / 2 ) ; if ( arr [ mid ] > val ) { right = mid - 1 ; } else { left = mid + 1 ; ind = mid ; } } return ind != - 1 ? ind - i + 1 : 1 ; } let arr = [ 1 , 3 , 5 , 9 , 14 ] ; let N = arr . length ; let D = 4 ; let minMax = minMaxRange ( arr , D , N ) ; document . write ( minMax [ 0 ] + " " + minMax [ 1 ] ) ;