Program to Find Union of Two Array.

Given two integer arrays, arr1[] and arr2[], the task is to find the union of the two arrays. The output should contain only distinct elements and the order of the elements in the output may vary.

Union of Array.

The union of two arrays is defined as the set of distinct elements that are present in either of the arrays. The resulting array must contain only unique elements, and the order of elements in the output may vary.

Example:

Input: arr1[] = {1, 2, 3, 4, 5}, arr2[] = {3, 4, 5, 6, 7}
Output: Union[] = {1, 2, 3, 4, 5, 6, 7}

Input: arr1[] = {4, 7, 9, 1}, arr2[] = {1, 5}
Output: Union[] = {1, 4, 5, 7, 9}

There are multiple methods to find the union of two arrays and here we are going to discuss a few of them in detail with code.

Approach 1: Brute Force.

The brute force approach involves iterating through both arrays and checking for each element if it's already in the result array. If not, add it to the result. This method ensures that the result contains only unique elements.

Step-by-step Algorithm to find the Union of Two Arrays:

STEP 1: Initialize an empty result[] array.
STEP 2: Iterate through arr1[] and arr2[].
STEP 3: For each element, check if it is not already in the result array.
STEP 4: If not, add it to the result[] array.
STEP 5: The result array is the union of arr1[] and arr2[].

C++ Code Implementation.

// C++ code to find Union of two arrays
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// function to find union of two arrays
vector<int> findUnionOfArrays(vector<int>& arr1, vector<int>& arr2) {
    vector<int> result;
    
    //insert the elements which are not present in result array
    for (int num : arr1) {
        if (find(result.begin(), result.end(), num) == result.end()) {
            result.push_back(num);
        }
    }

    for (int num : arr2) {
        if (find(result.begin(), result.end(), num) == result.end()) {
            result.push_back(num);
        }
    }

    return result;
}


int main() {
    vector<int> arr1 = {4, 9, 5, 1, 0};
    vector<int> arr2 = {9, 4, 9, 8, 4, 1};

    vector<int> result = findUnionOfArrays(arr1, arr2);

    // Print the Union of Two Arrays 
    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }

    return 0;
}

Output:

4 9 5 1 0 8

Time Complexity: O(m * n) where m and n are the sizes of arr1 and arr2.

Space Complexity: O(k) where k is the size of the result array.

Approach 2: Using Hash Map.

In this approach, we are using a Hash Map to keep track of unique elements.

Step-by-step to find the Union of Two Arrays.

STEP 1: Create a hash map to count occurrences of elements.
STEP 2: Iterate through arr1 and arr2, updating counts in the hash map.
STEP 3: Extract keys from the hash map to get the result.

C++ Code Implementation.

// C++ code to find Union of two arrays
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// function to find union of two arrays
vector<int> findUnionUsingHashMap(vector<int>& arr1, vector<int>& arr2) {
    unordered_map<int, int> countMap;

    for (int num : arr1) {
        countMap[num]++;
    }

    for (int num : arr2) {
        countMap[num]++;
    }

    vector<int> result;
    // store all unique elements to resultant array
    for (const auto& entry : countMap) {
        result.push_back(entry.first);
    }

    return result;
}

int main() {
    vector<int> arr1 = {4, 9, 5, 1, 0};
    vector<int> arr2 = {9, 4, 9, 8, 4, 1};

    vector<int> result = findUnionUsingHashMap(arr1, arr2);

    // Print the Union of Two Arrays 
    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }

    return 0;
}

Output:

8 0 1 5 9 4

Time Complexity: O(m + n) due to hash map operations.

Space Complexity: O(k) where k is the size of the result array.

(getButton) #text=(Program to Find Intersection of Two Arrays) #icon=(link) #color=(#2339bd)

Program to Find Union of Two Array.

Approach 1: Brute Force.

C++ Code Implementation.

Approach 2: Using Hash Map.

C++ Code Implementation.

No comments:

Post a Comment