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 ; Driver Code ; Given arrays ; Function call
def minElements ( A , B , N , M ) : NEW_LINE INDENT map = { } NEW_LINE for i in range ( len ( A ) ) : NEW_LINE INDENT map [ A [ i ] ] = i NEW_LINE DEDENT subseq = [ ] NEW_LINE l = 0 NEW_LINE r = - 1 NEW_LINE for i in range ( M ) : NEW_LINE INDENT if B [ i ] in map : NEW_LINE INDENT e = map [ B [ i ] ] NEW_LINE while ( l <= r ) : NEW_LINE INDENT m = l + ( r - l ) // 2 NEW_LINE if ( subseq [ m ] < e ) : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT else : NEW_LINE INDENT r = m - 1 NEW_LINE DEDENT DEDENT if ( r + 1 < len ( subseq ) ) : NEW_LINE INDENT subseq [ r + 1 ] = e NEW_LINE DEDENT else : NEW_LINE INDENT subseq . append ( e ) NEW_LINE DEDENT l = 0 NEW_LINE r = len ( subseq ) - 1 NEW_LINE DEDENT DEDENT return N - len ( subseq ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE B = [ 2 , 5 , 6 , 4 , 9 , 12 ] NEW_LINE M = len ( A ) NEW_LINE N = len ( B ) NEW_LINE print ( minElements ( A , B , M , N ) ) NEW_LINE DEDENT