Maximize Elements Using Another Array

Difficulty Level Medium
Frequently asked in Amazon Fanatics Fourkites
Array Hash SortingViews 2970

Suppose, we have given two integers array of same size n. Both of the arrays contain positive numbers. The problem statement asks to maximize the first array by using the second array element keeping the second array as a priority (elements of the second array should appear first in output). The array so formed should contain n unique but greatest elements of both the arrays.

Example

arr1[] = {3,7,9,1,4}
arr2[] = {2,8,6,5,3}
{8, 6, 5, 7, 9}
arr1[] = {9,3,2}
arr2[] = {6,4,1}
{6, 4, 9}

Algorithm

  1. Create an array of size 2*n.
  2. First store the second array elements into a created array and then first array elements.
  3. Sort the array in a non-ascending sequence.
  4. Store the n values of the array into the set.
  5. Arrange them in the order as they come as input by taking array2 first and checking if its element is present in the set and store them in the third array from the 0th index.
  6. Repeat the above process for the first array.
  7. Print the resultant array.

Explanation

We have two integers array. We need to maximize the first array in a way that the array so formed contains the second array element first and then the first array. It should contain the n unique and greatest elements from both the arrays. The order should be maintained that is if the element comes first then it should also come first in the second array. To solve this create an array of size 2*n because we have an array given as of size n and we just need to store the elements of both the arrays.

Store the elements of the second array firstly to the array we created and then store the elements of the first array to the created array. We are doing this because we are going to insert all the values of the created array to set. Because to solve this code we are going to use a set. After inserting all the values of the created array into the set. We will sort the array in a non-ascending sequence.

We will make a place in Set to insert the values from the array up to n times. N times is for, we already have the sorted array in non-ascending sequence, we just need the first n elements now to do some operations on it. After the insertion of Set, we have the greatest n values in the set. Now we need to arrange that value according to their order as they come in input, so we will traverse the array second firstly because that array is our priority. So if we found any of the elements of array second present in a Set. We will update that array created from the 0th position and also check for the first array as well and update its values in array third.

Now update the values of array3 to array1 and print array1, and that’s how we maximize the first array, taking the second array as a priority.

Implementation

C++ Program for Maximize Elements Using Another Array

#include <iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

bool compare(int a, int b)
{
    return a > b;
}
void getMaximizeArray(int arr1[], int arr2[], int n)
{
    int arr3[2*n], j = 0;
    for (int i = 0; i < n; i++)
        arr3[j++] = arr1[i];
    for (int i = 0; i < n; i++)
        arr3[j++] = arr2[i];

    unordered_set<int> SET;

    sort(arr3, arr3 + 2 * n, compare);

    int i = 0;
    while (SET.size() != n)
    {
        if (SET.find(arr3[i]) == SET.end())
            SET.insert(arr3[i]);

        i++;
    }
    j = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr2[i]) != SET.end())
        {
            arr3[j++] = arr2[i];
            SET.erase(arr2[i]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr1[i]) != SET.end())
        {
            arr3[j++] = arr1[i];
            SET.erase(arr1[i]);
        }
    }
    for (int i = 0; i < n; i++)
        arr1[i] = arr3[i];
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    getMaximizeArray(arr1, arr2, n);
    printArray(arr1, n);
}

8 6 5 7 9

Java Program for Maximize Elements Using Another Array

import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.lang.*;

class arrayMaximize
{
    public static void getMaximizeArray(int arr1[], int arr2[], int n)
    {
        int arr3[]=new int[2*n];
        int j = 0;
        for (int i = 0; i < n; i++)
            arr3[j++] = arr1[i];
        for (int i = 0; i < n; i++)
            arr3[j++] = arr2[i];


        Arrays.sort(arr3);

        HashSet<Integer> SET=new HashSet<>();

        int i = (2*n)-1;
        while (SET.size() != n)
        {
            if (!SET.contains(arr3[i]))
                SET.add(arr3[i]);

            i--;
        }


        j = 0;
        for (int a = 0; a < n; a++)
        {
            if (SET.contains(arr2[a]))
            {
                arr3[j++] = arr2[a];
                SET.remove(arr2[a]);
            }
        }

        for (int b = 0; b < n; b++)
        {
            if (SET.contains(arr1[b]))
            {
                arr3[j++] = arr1[b];
                SET.remove(arr1[b]);
            }
        }
        for (int c = 0; c < n; c++)
            arr1[c] = arr3[c];
    }
    public static void printArray(int arr[], int n)
    {
        for (int k = 0; k < n; k++)
            System.out.print(arr[k]+" ");
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        getMaximizeArray(arr1, arr2, n);
        printArray(arr1, n);
    }
}

8 6 5 7 9

Complexity Analysis for Maximize Elements Using Another Array

Time Complexity

O(n * log n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.

References

Translate »