Given two same sized arrays A and B (both arrays contain distinct elements individually but may have some common elements), task is to form a third (or result) array of same size. The result array should have maximum n elements from both array. It should have chosen elements of A first, then chosen elements of B in same order as they appear in original arrays. If there are common elements, then only one element should be present in res and priority should be given to A.
Input : A = [ 9 7 2 3 6 ] B = [ 7 4 8 0 1 ] Output : res = [9 7 6 4 8] res has maximum n elements of both A and B such that elements of A appear first (in same order), then elements of B. Also 7 is common and priority is given to A's 7. Input : A = [ 6 7 5 3 ] B = [ 5 6 2 9 ] Output : res = [ 6 7 5 9 ]
1) Create copies of both arrays and sort the copies in decreasing order.
2) Use a hash to pick unique n maximum elements of both arrays, giving priority to A.
3) Initialize result array as empty.
4) Traverse through A, copy those elements of A that are present in the hash. This is done to keep order of elements same.
5) Repeat step 4 for B. This time we only consider those elements that are not present in A (Do not appear twice in hash).
Below c++ implementation of above idea.
9 7 6 4 8
Time complexity: O(n Log n)