# Maximum array from two given arrays keeping order same

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[].

Examples:

```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 ]
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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.

 `// Make a set of maximum elements from two ` `// arrays A[] and B[] ` `#include ` `using` `namespace` `std; ` ` `  `void` `maximizeTheFirstArray(``int` `A[], ``int` `B[], ` `                                    ``int` `n) ` `{ ` `    ``// Create copies of A[] and B[] and sort ` `    ``// the copies in descending order. ` `    ``vector<``int``> temp1(A, A+n); ` `    ``vector<``int``> temp2(B, B+n); ` `    ``sort(temp1.begin(), temp1.end(), greater<``int``>()); ` `    ``sort(temp2.begin(), temp2.end(), greater<``int``>()); ` ` `  `    ``// Put maximum n distinct elements of ` `    ``// both sorted arrays in a map. ` `    ``unordered_map<``int``, ``int``> m; ` `    ``int` `i = 0, j = 0; ` `    ``while` `(m.size() < n) ` `    ``{ ` `         ``if` `(temp1[i] >= temp2[j]) ` `         ``{ ` `            ``m[temp1[i]]++; ` `            ``i++; ` `         ``} ` `         ``else` `         ``{ ` `            ``m[temp2[j]]++; ` `            ``j++; ` `         ``} ` `    ``} ` ` `  `    ``// Copy elements of A[] to that  ` `    ``// are present in hash m. ` `    ``vector<``int``> res; ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``if` `(m.find(A[i]) != m.end()) ` `           ``res.push_back(A[i]); ` ` `  `    ``// Copy elements of B[] to that  ` `    ``// are present in hash m. This time ` `    ``// we also check if the element did ` `    ``// not appear twice. ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``if` `(m.find(B[i]) != m.end() && ` `            ``m[B[i]] == 1) ` `           ``res.push_back(B[i]); ` ` `  `    ``// print result ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``cout << res[i] << ``" "``; ` `} ` ` `  `// driver program ` `int` `main() ` `{ ` `    ``int` `A[] = { 9, 7, 2, 3, 6 }; ` `    ``int` `B[] = { 7, 4, 8, 0, 1 }; ` `    ``int` `n = ``sizeof``(A) / ``sizeof``(A); ` `    ``maximizeTheFirstArray(A, B, n); ` `    ``return` `0; ` `} `

Output:

``` 9 7 6 4 8
```

Time complexity: O(n Log n)

This article is attributed to GeeksforGeeks.org

code

load comments