Maximum Array from Two given Arrays Keeping Order Same

Suppose we have two integers array of same size n. Both of the arrays can contain common numbers as well. The problem statement asks to form the resultant array that contains the ‘n’ maximum values from both of the arrays. The first array should be prioritized (elements of the first array should appear first in output). The output array would be of maximum elements from both of the given arrays but common elements should come once and prioritize the array first.

Table of Contents

Example

Input:

int arr1[] = {3,7,9,1,4}

int arr2[] = {2,8,6,5,3}

Output:

{7, 9, 8, 6, 5}

Explanation:

As 7, 9 are the elements in the first array, so that it comes first in the output.

Input:

int arr1[] = {9,3,2}

int arr2[] = {6,4,1}

Output:

{9, 6, 4}

Algorithm for Maximum Array from Two given Arrays Keeping Order Same

Convert both of the arrays into the vector.
Sort both of the vectors in a non-ascending sequence.
Traverse both of the vectors simultaneously, and push ‘n’ bigger values of both of the vectors into the map along with the element’s frequency.
Create a new vector “output”.
Check if there is a common element in a map and also in an array first, then, add that element into the output vector.
Check, if there is a common element in a map and also in array second, then, select those whose frequency is 1, and add them into the output vector.
Print the resultant vector “output”.

Explanation

Converting both of the arrays into the vector and sort them in decreasing order. With this, we can get the values of both of the arrays into the vector and we have bigger numbers first in a sequence in both of the vectors. So, we can choose ‘n’ maximum number from both of the arrays.

To handle the case of common elements what we are going to do is, simultaneously comparing the vectors and picking the maximum from both of the arrays, and put it into the map with their frequency, with this we can maintain an eye for if there can be common elements, we will be pushing n maximum elements into the map, if we found one element more than once, we are just going to increase their frequency and they won’t be count as an extra element in a map, they will be marked as frequency 2, 3 or more.. so, in later traversal, we can ignore it and can prioritize the first array.

We are going to traverse both, the arrays and the map. First, we need to traverse the first array with the map, if any of the common elements found in a map as well as in an array, we need to push it into the output vector, which we created as a resultant. Then we will traverse the second array since the common element could also be stored in the resultant, so here along with the common value from the second array and a map, we are going to check if that element has a frequency of 1 in the map, then only we will be pushing it into the resultant vector. And finally, print that vector.

Implementation

C++ program for Maximum Array from Two given Arrays Keeping Order Same

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

void makeGreaterFirstArray(int A[], int B[], int n)
{
    vector<int> V1(A, A+n);
    vector<int> V2(B, B+n);
    sort(V1.begin(), V1.end(), greater<int>());
    sort(V2.begin(), V2.end(), greater<int>());

    unordered_map<int, int> MAP;
    int i = 0, j = 0;
    while (MAP.size() < n)
    {
        if (V1[i] >= V2[j])
        {
            MAP[V1[i]]++;
            i++;
        }
        else
        {
            MAP[V2[j]]++;
            j++;
        }
    }
    vector<int> output;
    for (int i = 0; i < n; i++)
        if (MAP.find(A[i]) != MAP.end())
            output.push_back(A[i]);

    for (int i = 0; i < n; i++)
        if (MAP.find(B[i]) != MAP.end() && MAP[B[i]] == 1)
            output.push_back(B[i]);

    for (int i = 0; i < n; i++)
        cout << output[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    makeGreaterFirstArray(arr1, arr2, n);
    return 0;
}

7 9 8 6 5

Java program for Maximum Array from Two given Arrays Keeping Order Same

import java.util.Collections;
import java.util.Vector;
import java.util.HashMap;
import java.util.Arrays;
import java.util.stream.Collectors;

class findsubarray
{
    public static void makeGreaterFirstArray(int []A, int []B, int n)
    {
        Vector<Integer> V1 = new Vector<>();
        Vector<Integer> V2 = new Vector<>();

        Integer[] I1 = Arrays.stream( A ).boxed().toArray( Integer[]::new );
        Integer[] I2 = Arrays.stream( B ).boxed().toArray( Integer[]::new );


        Collections.addAll(V1, I1);
        Collections.addAll(V2, I2);

        Collections.sort(V1, Collections.reverseOrder());
        Collections.sort(V2, Collections.reverseOrder());


        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int i = 0, j = 0;
        while (MAP.size() < n)
        {
            if (V1.get(i) >= V2.get(j))
            {
                if(MAP.containsKey(V1.get(i)))
                {
                    MAP.put(V1.get(i), MAP.get(V1.get(i))+1);
                    i++;
                }
                else
                {
                    MAP.put(V1.get(i),1);
                    i++;
                }
            }
            else
            {
                if(MAP.containsKey(V2.get(j)))
                {
                    MAP.put(V2.get(j), MAP.get(V2.get(j))+1);
                    j++;
                }
                else
                {
                    MAP.put(V2.get(j),1);
                    j++;
                }
            }
        }
        Vector<Integer> output = new Vector<Integer>();

        for (int a = 0; a < n; a++)
            if (MAP.containsKey(A[a]))
                output.add(A[a]);

        for (int b = 0; b < n; b++)
            if (MAP.containsKey(B[b]) && MAP.get(B[b])==1)
                output.add(B[b]);


        System.out.println(output);
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        makeGreaterFirstArray(arr1, arr2, n);
    }
}

[7, 9, 8, 6, 5]