s | Java program for the above approach ; To sort the array and return the answer ; sort the array ; fill all stated with - 1 when only one element ; as dp [ 0 ] = 0 ( base case ) so min no of elements to be removed are n - 1 elements ; Iterate from 1 to n - 1 ; Driver code
import java . io . * ; import java . util . * ; class GFG { static int removals ( int arr [ ] , int n , int k ) { Arrays . sort ( arr ) ; int dp [ ] = new int [ n ] ; Arrays . fill ( dp , - 1 ) ; int ans = n - 1 ; dp [ 0 ] = 0 ; for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] = i ; int j = dp [ i - 1 ] ; while ( j != i && arr [ i ] - arr [ j ] > k ) { j ++ ; } dp [ i ] = Integer . min ( dp [ i ] , j ) ; ans = Integer . min ( ans , ( n - ( i - j + 1 ) ) ) ; } return ans ; } public static void main ( String [ ] args ) { int a [ ] = { 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 } ; int n = a . length ; int k = 4 ; System . out . print ( removals ( a , n , k ) ) ; } }