Minimum and maximum count of elements at D distance from arr [ i ] in either direction | Java program for the above approach ; 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
import java . io . * ; import java . lang . Math ; import java . util . * ; class GFG { public static int [ ] minMaxRange ( int [ ] arr , int D , int N ) { int max = 1 , min = N ; for ( int i = 0 ; i < N ; i ++ ) { int 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 new int [ ] { min , max } ; } public static int leftSearch ( int [ ] arr , int val , int i ) { if ( i == 0 ) return 1 ; int left = 0 , right = i - 1 ; int ind = - 1 ; while ( left <= right ) { int mid = ( left + right ) / 2 ; if ( arr [ mid ] < val ) { left = mid + 1 ; } else { right = mid - 1 ; ind = mid ; } } return ind != - 1 ? i - ind + 1 : 1 ; } public static int rightSearch ( int [ ] arr , int val , int i ) { if ( i == arr . length - 1 ) return 1 ; int left = i + 1 ; int right = arr . length - 1 ; int ind = - 1 ; while ( left <= right ) { int mid = ( left + right ) / 2 ; if ( arr [ mid ] > val ) { right = mid - 1 ; } else { left = mid + 1 ; ind = mid ; } } return ind != - 1 ? ind - i + 1 : 1 ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 3 , 5 , 9 , 14 } ; int N = arr . length ; int D = 4 ; int [ ] minMax = minMaxRange ( arr , D , N ) ; System . out . print ( minMax [ 0 ] + " ▁ " + minMax [ 1 ] ) ; } }