Minimize elements to be added to a given array such that it contains another given array as its subsequence | Set 2 | Java program for the above approach ; 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
import java . util . * ; import java . lang . * ; class GFG { static int minElements ( int [ ] A , int [ ] B , int N , int M ) { Map < Integer , Integer > map = new HashMap < > ( ) ; for ( int i = 0 ; i < A . length ; i ++ ) { map . put ( A [ i ] , i ) ; } ArrayList < Integer > subseq = new ArrayList < > ( ) ; int l = 0 , r = - 1 ; for ( int i = 0 ; i < M ; i ++ ) { if ( map . containsKey ( B [ i ] ) ) { int e = map . get ( B [ i ] ) ; while ( l <= r ) { int m = l + ( r - l ) / 2 ; if ( subseq . get ( m ) < e ) l = m + 1 ; else r = m - 1 ; } if ( r + 1 < subseq . size ( ) ) { subseq . set ( r + 1 , e ) ; } else { subseq . add ( e ) ; } l = 0 ; r = subseq . size ( ) - 1 ; } } return N - subseq . size ( ) ; } public static void main ( String [ ] args ) { int [ ] A = { 1 , 2 , 3 , 4 , 5 } ; int [ ] B = { 2 , 5 , 6 , 4 , 9 , 12 } ; int M = A . length ; int N = B . length ; System . out . println ( minElements ( A , B , M , N ) ) ; } }