Minimize count of array elements to be removed such that at least K elements are equal to their index values | Function to minimize the removals of array elements such that atleast K elements are equal to their indices ; Store the array as 1 - based indexing Copy of first array ; Make a dp - table of ( N * N ) size ; Delete the current element ; Take the current element ; Check for the minimum removals ; Driver Code
function MinimumRemovals ( a , N , K ) { let b = new Array ( N + 1 ) ; for ( let i = 0 ; i < N ; i ++ ) { b [ i + 1 ] = a [ i ] ; } let dp = new Array ( N + 1 ) . fill ( 0 ) . map ( ( ) => new Array ( N + 1 ) . fill ( 0 ) ) ; for ( let i = 0 ; i < N ; i ++ ) { for ( let j = 0 ; j <= i ; j ++ ) { dp [ i + 1 ] [ j ] = Math . max ( dp [ i + 1 ] [ j ] , dp [ i ] [ j ] ) ; dp [ i + 1 ] [ j + 1 ] = Math . max ( dp [ i + 1 ] [ j + 1 ] , dp [ i ] [ j ] + ( ( b [ i + 1 ] == j + 1 ) ? 1 : 0 ) ) ; } } for ( let j = N ; j >= 0 ; j -- ) { if ( dp [ N ] [ j ] >= K ) { return ( N - j ) ; } } return - 1 ; } let arr = [ 5 , 1 , 3 , 2 , 3 ] ; let K = 2 ; let N = arr . length document . write ( MinimumRemovals ( arr , N , K ) ) ;