s | 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
function removals ( arr , n , k ) { arr . sort ( ( a , b ) => a - b ) ; var dp = Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) dp [ i ] = - 1 ; var ans = n - 1 ; dp [ 0 ] = 0 ; for ( var i = 1 ; i < n ; i ++ ) { dp [ i ] = i ; var j = dp [ i - 1 ] ; while ( j != i && arr [ i ] - arr [ j ] > k ) { j ++ ; } dp [ i ] = Math . min ( dp [ i ] , j ) ; ans = Math . min ( ans , ( n - ( i - j + 1 ) ) ) ; } return ans ; } var a = [ 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 ] ; var n = a . length ; var k = 4 ; document . write ( removals ( a , n , k ) ) ;