Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement 
1.2.
Sample example 
2.
Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.3.
Implementation in Java
2.4.
Complexity analysis
3.
Frequently Asked Questions
3.1.
In Java, what is the default value of Array?
3.2.
What is the distinction between an array and an object?
3.3.
Can we change the size of an array at run time?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Maximize elements using another array

Author Shivani Singh
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

In Java, what is the default value of Array?

If we do not specify the values, Java assigns default values, which are 0 for byte, short, int, and long, 0.0 for float and double, false for boolean, and null for objects.

What is the distinction between an array and an object?

An object represents a thing with properties, whereas an array generates a list of data and stores it in a single variable. We can access, alter, and delete objects using brackets and dots, while arrays can be accessed and modified using a variety of built-in methods and zero-based indexing.

Can we change the size of an array at run time?

No, we cannot change the size of the array. But there are related data types that allow for size changes.

Conclusion

To conclude this blog, firstly we discussed the problem statement and ways to solve the problems. For the naive approach, we discussed its algorithm, pseudo-code, and complexities.

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Number of subsets with product less than k
Next article
Minimum product of k integers in an array of positive Integers
Live masterclass