Introduction
Here in this blog, we are asked to maximize elements using another array. We have already a clear idea of data structures and algorithms. So, let's delve a little deeper into this blog.
Problem statement
Assume we have two integer arrays of the same size n. Positive numbers are present in both arrays. The problem statement instructs you to maximize the first array by using the second array element while prioritizing the second array (elements of the second array should appear first in output). The resulting array should contain n distinct but greatest elements from both arrays.
Let us understand this with the help of an example.
Source: array
Sample example
Assume that the first array arr1 is: {3,7,9,1,4} and second array arr2 is: {2,8,6,5,3}.
As we have to maximize the first array using the second array. In the second array, the greatest elements are 8,6,5 and in the first array, the greatest elements are 7,9. So we have to return these greatest values in the first array only.
The problem statement is quite clear with the above example.
From the above diagram, we can clearly see the new array will become {8,6,5,7,9}. As it is said in the problem statement itself that the elements of the second array should appear first. So, 8,6,5 comes first and after them 7,9 respectively.
Approach
This approach is very simple to implement. In this approach, we will use an auxiliary array of size 2*n. In this auxiliary array, we will first store the elements of the second array and after it elements of the first array. Then we will sort this array into descending order. For the in place of the elements, we will take the help of a hash table or set. Let us see the algorithm of this approach.
Steps of Algorithm
Step 1: Make a 2*n-dimensional auxiliary array.
Step 2: First, put the second array elements into a newly created array, followed by the first array elements.
Step 3: Sort the array in descending order.
Step 4: Insert the array's n values into the set (or hash table).
Step 5: Arrange them in the order they are given as input by taking arr2 first and checking if its element is in the set, then storing them in the third array starting at the 0th index.
Step 6: Repeat step 5 for the first array arr1 also.
Step 7: Display the resulting array.
Let us see the implementation of this approach in the next section of this blog.
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
bool maximum(int a, int b)
{
return a > b;
}
void MaximizeArray(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, maximum);
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 DisplayArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main()
{
int arr1[] = {9,10,8};
int arr2[] = {7,6,11};
int n = sizeof(arr1) / sizeof(arr1[0]);
MaximizeArray(arr1, arr2, n);
cout<<"The maximize array is: "<<endl;
DisplayArray(arr1, n);
}
Output:
The maximize array is:
11 9 10 Implementation in Java
import java.util.*;
class MaximizeArray
{
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 c = 0; c < n; c++)
{
if (set.contains(arr2[c]))
{
arr3[j++] = arr2[c];
set.remove(arr2[c]);
}
}
for (int l = 0; l < n; l++)
{
if (set.contains(arr1[l]))
{
arr3[j++] = arr1[l];
set.remove(arr1[l]);
}
}
for (int m = 0; m < n; m++)
arr1[m] = arr3[m];
}
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[] = {9,10,8};
int arr2[] = {7,6,11};
int n = arr1.length;
System.out.println("The maximize array is: ");
getMaximizeArray(arr1, arr2, n);
printArray(arr1, n);
}
}
Output:
The maximize array is: 11 9 10
Let us analyze the time and complexity of this approach.
Complexity analysis
Time complexity
This approach will take O(n log n ), where n is the number of elements. In this approach, we are using an auxiliary array and also copying the elements of the first array into the auxiliary array. Then most important, we are also sorting the elements of the arrays. So this approach will take O(n log n).
Space complexity
It will take O(n), where n is the number of elements.
Source: complexity
Also see, Rabin Karp Algorithm
117+ registered 