Minimize elements to be added to a given array such that it contains another given array as its subsequence | Set 2 | Function to return minimum element to be added in array B so that array A become subsequence of array B ; Stores indices of the array elements ; Iterate over the array ; Store the indices of the array elements ; Stores the LIS ; Check if element B [ i ] is in array A [ ] ; Perform Binary Search ; Find the value of mid m ; Update l and r ; If found better element ' e ' for pos r + 1 ; Otherwise , extend the current subsequence ; Return the answer ; Given arrays ; Function Call
function minElements ( A , B , N , M ) { var map = new Map ( ) ; for ( var i = 0 ; i < N ; i ++ ) { map . set ( A [ i ] , i ) ; } var subseq = [ ] ; var l = 0 , r = - 1 ; for ( var i = 0 ; i < M ; i ++ ) { if ( map . has ( B [ i ] ) ) { var e = map . get ( B [ i ] ) ; while ( l <= r ) { var m = l + parseInt ( ( r - l ) / 2 ) ; if ( subseq [ m ] < e ) l = m + 1 ; else r = m - 1 ; } if ( r + 1 < subseq . length ) { subseq [ r + 1 ] = e ; } else { subseq . push ( e ) ; } l = 0 ; r = subseq . length - 1 ; } } return N - subseq . length ; } var A = [ 1 , 2 , 3 , 4 , 5 ] ; var B = [ 2 , 5 , 6 , 4 , 9 , 12 ] ; var M = A . length ; var N = B . length ; document . write ( minElements ( A , B , M , N ) ) ;