Merge two Maps of Array into one sorted Map of Array

0 1 10 minutes read

Given two maps map1 and map2 having a string as the key and arrays of integers as values, the task is to merge them in one map such that if a key is common in both the maps, the respective arrays should be merged.

Examples:

Input: map1 = { (“key1”, {0, 1}), (“key2”, {0, 1}) }, map2 = { (“key2”, {1, 2}) };
Output: { (key1, {0, 1}), (key2, {0, 1, 2}) }
Explanation: After merging key1 array will become {0, 1} and for key2 after merging array will become {0, 1, 2}

Input: map1 = {(“key1”, {0, 1})}, map2 = {(“key2”, {1, 2})};
Output: {(key1, [0, 1]), (key2, [1, 2])}

Approach: The solution to the problem is based on the concept of merging two arrays. Follow the steps mentioned below:

Create a map to store the merged maps
Traverse map1 and store all the key-value pairs in map1.
Traverse map2 and:
- If the key of map2 does not exists in map1, just insert this key value pair in map1
- If the key of map2 exists in map1,
  - Take the array of map1 and array of map2
  - Sort both the arrays, and
  - Merge them using approach mentioned in merge two arrays.
Return the map3 at the end.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to merge arrays
vector<int> mergeArrays(vector<int>& a, vector<int>& b,
                        int n, int m)
{
    vector<int> mergedArray;
 
    // Declaring a map.
    // Using map as a inbuilt tool
    // to store elements in sorted order.
    map<int, bool> mp;
 
    // Inserting values to a map.
    for (int i = 0; i < n; i++)
        mp[a[i]] = true;
 
    for (int i = 0; i < m; i++)
        mp[b[i]] = true;
 
    // Printing keys of the map.
    for (auto i : mp)
        mergedArray.push_back(i.first);
    return mergedArray;
}
 
// Function to merge maps
map<string, vector<int> >
mergeMap(map<string, vector<int> >& map1,
         map<string, vector<int> >& map2)
{
    map<string, vector<int> > map3;
    map3.insert(map1.begin(), map1.end());
 
    for (auto itr : map2) {
        if (map3.find(itr.first) == map3.end())
            map3.insert({ itr.first, itr.second });
        else {
            auto temp_itr = map3.find(itr.first);
            vector<int> arr = mergeArrays(
                itr.second, temp_itr->second,
                itr.second.size(),
                temp_itr->second.size());
            map3[itr.first] = arr;
        }
    }
    return map3;
}
 
// Driver code
int main()
{
    map<string, vector<int> > map1, map2, map3;
    map1.insert({ "key1", { 0, 1 } });
    map1.insert({ "key2", { 0, 1 } });
    map2.insert({ "key2", { 1, 2 } });
 
    // Function call
    map3 = mergeMap(map1, map2);
 
    for (auto itr : map3) {
        cout << "\"" << itr.first << "\", { ";
        for (auto x : itr.second)
            cout << x << " ";
        cout << "}\n";
    }
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.util.*;
 
class GFG {
 public static Vector<Integer> mergeArrays(Vector<Integer> a, 
                                           Vector<Integer> b, int n, int m) {
    Vector<Integer> mergedArray = new Vector<Integer>();
 
    // Declaring a map.
    // Using map as a inbuilt tool
    // to store elements in sorted order.
    Map<Integer, Boolean> mp = new HashMap<Integer, Boolean>();
 
    // Inserting values to a map.
    for (int i = 0; i < n; i++)
        mp.put(a.get(i), true);
 
    for (int i = 0; i < m; i++)
        mp.put(b.get(i), true);
 
    // Printing keys of the map.
    for (Map.Entry<Integer, Boolean> i : mp.entrySet())
        mergedArray.add(i.getKey());
    return mergedArray;
}
 
public static Map<String, Vector<Integer>> mergeMap(Map<String, 
                          Vector<Integer>> map1, Map<String, Vector<Integer>> map2) {
    Map<String, Vector<Integer>> map3 = new HashMap<String, Vector<Integer>>();
    map3.putAll(map1);
 
    for (Map.Entry<String, Vector<Integer>> itr : map2.entrySet()) {
        if (!map3.containsKey(itr.getKey()))
            map3.put(itr.getKey(), itr.getValue());
        else {
            Vector<Integer> temp_itr = map3.get(itr.getKey());
            Vector<Integer> arr = mergeArrays(itr.getValue(), 
                                 temp_itr, itr.getValue().size(), temp_itr.size());
            map3.put(itr.getKey(), arr);
        }
    }
    return map3;
}
 
public static void main(String[] args) {
    Map<String, Vector<Integer>> map1 = new HashMap<String, Vector<Integer>>();
    Map<String, Vector<Integer>> map2 = new HashMap<String, Vector<Integer>>();
    Map<String, Vector<Integer>> map3 = new HashMap<String, Vector<Integer>>();
    map1.put("key1", new Vector<Integer>(Arrays.asList(0, 1)));
    map1.put("key2", new Vector<Integer>(Arrays.asList(0, 1)));
    map2.put("key2", new Vector<Integer>(Arrays.asList(1, 2)));
 
    map3 = mergeMap(map1, map2);
 
    for (Map.Entry<String, Vector<Integer>> itr : map3.entrySet()) {
        System.out.print("\"" + itr.getKey() + "\", { ");
        for (int x : itr.getValue())
            System.out.print(x + " ");
        System.out.println("}");
    }
}
}

Python3

# Python code to implement the approach
 
# Function to merge arrays
def mergeArrays (a, b, n, m):
    mergedArray = [];
 
    # Declaring a map.
    # Using map as a inbuilt tool
    # to store elements in sorted order.
    mp = {};
 
    # Inserting values to a map.
    for i in range(n):
        mp[a[i]] = True;
 
    for i in range(m):
        mp[b[i]] = True;
 
    # Printing keys of the map.
    for i in mp:
        mergedArray.append(i);
 
    return mergedArray;
 
# Function to merge maps
def mergeMap (map1, map2):
    map3 = {};
    for itm in map1.keys():
        map3[itm] = map1[itm];
 
    for itr in map2.keys():
        if (not itr in map3.keys()):
            map3[itr] = map2[itr];
        else:
            arr = mergeArrays(map2[itr], map3[itr], len(map2[itr]), len(map3[itr]));
 
            map3[itr] = arr;
 
    return map3;
 
# Driver code
map1 = {}
map2 = {}
map3 = {};
 
map1["key1"] = [0, 1];
map1["key2"] = [0, 1];
map2["key2"] = [1, 2];
 
# Function call
map3 = mergeMap(map1, map2);
 
for itr in map3.keys():
    print(f"\"{itr}\", {{", end=" ")
    map3[itr].sort()
    for x in map3[itr]:
        print(map3[itr][x], end=" ");
    print("} ");
 
# This code is contributed by Saurabh Jaiswal

Javascript

<script>
    // JavaScript code to implement the approach
 
    // Function to merge arrays
    const mergeArrays = (a, b, n, m) => {
        let mergedArray = [];
 
        // Declaring a map.
        // Using map as a inbuilt tool
        // to store elements in sorted order.
        let mp = {};
 
        // Inserting values to a map.
        for (let i = 0; i < n; i++)
            mp[a[i]] = true;
 
        for (let i = 0; i < m; i++)
            mp[b[i]] = true;
 
        // Printing keys of the map.
        for (let i in mp)
            mergedArray.push(i);
        return mergedArray;
    }
 
    // Function to merge maps
    const mergeMap = (map1, map2) => {
        let map3 = {};
        for (let itm in map1) map3[itm] = map1[itm];
 
        for (let itr in map2) {
            if (!(itr in map3))
                map3[itr] = map2[itr];
            else {
                let arr = mergeArrays(map2[itr], map3[itr], map2[itr].length, map3[itr].length);
 
                map3[itr] = arr;
            }
        }
        return map3;
    }
 
    // Driver code
 
    let map1 = {}, map2 = {}, map3 = {};
 
    map1["key1"] = [0, 1];
    map1["key2"] = [0, 1];
    map2["key2"] = [1, 2];
 
    // Function call
    map3 = mergeMap(map1, map2);
 
    for (let itr in map3) {
        document.write(`"${itr}", { `);
        for (let x in map3[itr])
            document.write(`${map3[itr][x]} `);
        document.write("}<br/>");
    }
 
// This code is contributed by rakeshsahni
 
</script>

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
namespace MergeMaps
{
    class Program
    {
        // Function to merge arrays
        static List<int> MergeArrays(List<int> a, List<int> b, int n, int m)
        {
            List<int> mergedArray = new List<int>();
 
            // Declaring a dictionary
            Dictionary<int, bool> dict = new Dictionary<int, bool>();
 
            // Inserting values to a dictionary
            foreach (int i in a)
                dict[i] = true;
 
            foreach (int i in b)
                dict[i] = true;
 
            // Printing keys of the dictionary
            foreach (var i in dict.Keys)
                mergedArray.Add(i);
 
            return mergedArray;
        }
 
        // Function to merge dictionaries
        static Dictionary<string, List<int>> MergeMap(Dictionary<string, List<int>> map1, Dictionary<string, List<int>> map2)
        {
            Dictionary<string, List<int>> map3 = new Dictionary<string, List<int>>();
            foreach (var item in map1)
                map3[item.Key] = item.Value;
 
            foreach (var itr in map2)
            {
                if (!map3.ContainsKey(itr.Key))
                    map3[itr.Key] = itr.Value;
                else
                {
                    var temp_itr = map3[itr.Key];
                    List<int> arr = MergeArrays(itr.Value, temp_itr, itr.Value.Count, temp_itr.Count);
                    map3[itr.Key] = arr;
                }
            }
            return map3;
        }
 
        static void Main(string[] args)
        {
            Dictionary<string, List<int>> map1 = new Dictionary<string, List<int>>();
            Dictionary<string, List<int>> map2 = new Dictionary<string, List<int>>();
            Dictionary<string, List<int>> map3 = new Dictionary<string, List<int>>();
 
            map1["key1"] = new List<int> { 0, 1 };
            map1["key2"] = new List<int> { 0, 1 };
            map2["key2"] = new List<int> { 1, 2 };
 
            // Function call
            map3 = MergeMap(map1, map2);
 
            foreach (var itr in map3)
            {
                Console.Write("\"" + itr.Key + "\", { ");
                foreach (var x in itr.Value)
                    Console.Write(x + " ");
                Console.WriteLine("}");
            }
        }
    }
}

Output

"key1", { 0 1 }
"key2", { 0 1 2 }

Time Complexity: O(N * log N + M * log M)
Auxiliary Space: O(M + N

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to merge arrays
vector<int> mergeArrays(vector<int>& a, vector<int>& b,
                        int n, int m)
{
    vector<int> mergedArray;
 
    // Declaring a map.
    // Using map as a inbuilt tool
    // to store elements in sorted order.
    map<int, bool> mp;
 
    // Inserting values to a map.
    for (int i = 0; i < n; i++)
        mp[a[i]] = true;
 
    for (int i = 0; i < m; i++)
        mp[b[i]] = true;
 
    // Printing keys of the map.
    for (auto i : mp)
        mergedArray.push_back(i.first);
    return mergedArray;
}
 
// Function to merge maps
map<string, vector<int> >
mergeMap(map<string, vector<int> >& map1,
         map<string, vector<int> >& map2)
{
    map<string, vector<int> > map3;
    map3.insert(map1.begin(), map1.end());
 
    for (auto itr : map2) {
        if (map3.find(itr.first) == map3.end())
            map3.insert({ itr.first, itr.second });
        else {
            auto temp_itr = map3.find(itr.first);
            vector<int> arr = mergeArrays(
                itr.second, temp_itr->second,
                itr.second.size(), temp_itr->second.size());
            map3[itr.first] = arr;
        }
    }
    return map3;
}
 
// Driver code
int main()
{
    map<string, vector<int> > map1, map2, map3;
    map1.insert({ "key1", { 0, 1 } });
    map1.insert({ "key2", { 0, 1 } });
    map2.insert({ "key2", { 1, 2 } });
 
    // Function call
    map3 = mergeMap(map1, map2);
 
    for (auto itr : map3) {
        cout << "\"" << itr.first << "\", { ";
        for (auto x : itr.second)
            cout << x << " ";
        cout << "}\n";
    }
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.util.*;
 
class GFG {
 public static Vector<Integer> mergeArrays(Vector<Integer> a, 
                                           Vector<Integer> b, int n, int m) {
    Vector<Integer> mergedArray = new Vector<Integer>();
 
    // Declaring a map.
    // Using map as a inbuilt tool
    // to store elements in sorted order.
    Map<Integer, Boolean> mp = new HashMap<Integer, Boolean>();
 
    // Inserting values to a map.
    for (int i = 0; i < n; i++)
        mp.put(a.get(i), true);
 
    for (int i = 0; i < m; i++)
        mp.put(b.get(i), true);
 
    // Printing keys of the map.
    for (Map.Entry<Integer, Boolean> i : mp.entrySet())
        mergedArray.add(i.getKey());
    return mergedArray;
}
 
public static Map<String, Vector<Integer>> mergeMap(Map<String, 
                          Vector<Integer>> map1, Map<String, Vector<Integer>> map2) {
    Map<String, Vector<Integer>> map3 = new HashMap<String, Vector<Integer>>();
    map3.putAll(map1);
 
    for (Map.Entry<String, Vector<Integer>> itr : map2.entrySet()) {
        if (!map3.containsKey(itr.getKey()))
            map3.put(itr.getKey(), itr.getValue());
        else {
            Vector<Integer> temp_itr = map3.get(itr.getKey());
            Vector<Integer> arr = mergeArrays(itr.getValue(), 
                                 temp_itr, itr.getValue().size(), temp_itr.size());
            map3.put(itr.getKey(), arr);
        }
    }
    return map3;
}
 
public static void main(String[] args) {
    Map<String, Vector<Integer>> map1 = new HashMap<String, Vector<Integer>>();
    Map<String, Vector<Integer>> map2 = new HashMap<String, Vector<Integer>>();
    Map<String, Vector<Integer>> map3 = new HashMap<String, Vector<Integer>>();
    map1.put("key1", new Vector<Integer>(Arrays.asList(0, 1)));
    map1.put("key2", new Vector<Integer>(Arrays.asList(0, 1)));
    map2.put("key2", new Vector<Integer>(Arrays.asList(1, 2)));
 
    map3 = mergeMap(map1, map2);
 
    for (Map.Entry<String, Vector<Integer>> itr : map3.entrySet()) {
        System.out.print("\"" + itr.getKey() + "\", { ");
        for (int x : itr.getValue())
            System.out.print(x + " ");
        System.out.println("}");
    }
}
}

Python3

# Python code to implement the approach
 
# Function to merge arrays
def mergeArrays (a, b, n, m):
    mergedArray = [];
 
    # Declaring a map.
    # Using map as a inbuilt tool
    # to store elements in sorted order.
    mp = {};
 
    # Inserting values to a map.
    for i in range(n):
        mp[a[i]] = True;
 
    for i in range(m):
        mp[b[i]] = True;
 
    # Printing keys of the map.
    for i in mp:
        mergedArray.append(i);
 
    return mergedArray;
 
# Function to merge maps
def mergeMap (map1, map2):
    map3 = {};
    for itm in map1.keys():
        map3[itm] = map1[itm];
 
    for itr in map2.keys():
        if (not itr in map3.keys()):
            map3[itr] = map2[itr];
        else:
            arr = mergeArrays(map2[itr], map3[itr], len(map2[itr]), len(map3[itr]));
 
            map3[itr] = arr;
 
    return map3;
 
# Driver code
map1 = {}
map2 = {}
map3 = {};
 
map1["key1"] = [0, 1];
map1["key2"] = [0, 1];
map2["key2"] = [1, 2];
 
# Function call
map3 = mergeMap(map1, map2);
 
for itr in map3.keys():
    print(f"\"{itr}\", {{", end=" ")
    map3[itr].sort()
    for x in map3[itr]:
        print(map3[itr][x], end=" ");
    print("} ");
 
# This code is contributed by Saurabh Jaiswal

Javascript

<script>
    // JavaScript code to implement the approach
 
    // Function to merge arrays
    const mergeArrays = (a, b, n, m) => {
        let mergedArray = [];
 
        // Declaring a map.
        // Using map as a inbuilt tool
        // to store elements in sorted order.
        let mp = {};
 
        // Inserting values to a map.
        for (let i = 0; i < n; i++)
            mp[a[i]] = true;
 
        for (let i = 0; i < m; i++)
            mp[b[i]] = true;
 
        // Printing keys of the map.
        for (let i in mp)
            mergedArray.push(i);
        return mergedArray;
    }
 
    // Function to merge maps
    const mergeMap = (map1, map2) => {
        let map3 = {};
        for (let itm in map1) map3[itm] = map1[itm];
 
        for (let itr in map2) {
            if (!(itr in map3))
                map3[itr] = map2[itr];
            else {
                let arr = mergeArrays(map2[itr], map3[itr], map2[itr].length, map3[itr].length);
 
                map3[itr] = arr;
            }
        }
        return map3;
    }
 
    // Driver code
 
    let map1 = {}, map2 = {}, map3 = {};
 
    map1["key1"] = [0, 1];
    map1["key2"] = [0, 1];
    map2["key2"] = [1, 2];
 
    // Function call
    map3 = mergeMap(map1, map2);
 
    for (let itr in map3) {
        document.write(`"${itr}", { `);
        for (let x in map3[itr])
            document.write(`${map3[itr][x]} `);
        document.write("}<br/>");
    }
 
// This code is contributed by rakeshsahni
 
</script>

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
namespace MergeMaps
{
    class Program
    {
        // Function to merge arrays
        static List<int> MergeArrays(List<int> a, List<int> b, int n, int m)
        {
            List<int> mergedArray = new List<int>();
 
            // Declaring a dictionary
            Dictionary<int, bool> dict = new Dictionary<int, bool>();
 
            // Inserting values to a dictionary
            foreach (int i in a)
                dict[i] = true;
 
            foreach (int i in b)
                dict[i] = true;
 
            // Printing keys of the dictionary
            foreach (var i in dict.Keys)
                mergedArray.Add(i);
 
            return mergedArray;
        }
 
        // Function to merge dictionaries
        static Dictionary<string, List<int>> MergeMap(Dictionary<string, List<int>> map1, Dictionary<string, List<int>> map2)
        {
            Dictionary<string, List<int>> map3 = new Dictionary<string, List<int>>();
            foreach (var item in map1)
                map3[item.Key] = item.Value;
 
            foreach (var itr in map2)
            {
                if (!map3.ContainsKey(itr.Key))
                    map3[itr.Key] = itr.Value;
                else
                {
                    var temp_itr = map3[itr.Key];
                    List<int> arr = MergeArrays(itr.Value, temp_itr, itr.Value.Count, temp_itr.Count);
                    map3[itr.Key] = arr;
                }
            }
            return map3;
        }
 
        static void Main(string[] args)
        {
            Dictionary<string, List<int>> map1 = new Dictionary<string, List<int>>();
            Dictionary<string, List<int>> map2 = new Dictionary<string, List<int>>();
            Dictionary<string, List<int>> map3 = new Dictionary<string, List<int>>();
 
            map1["key1"] = new List<int> { 0, 1 };
            map1["key2"] = new List<int> { 0, 1 };
            map2["key2"] = new List<int> { 1, 2 };
 
            // Function call
            map3 = MergeMap(map1, map2);
 
            foreach (var itr in map3)
            {
                Console.Write("\"" + itr.Key + "\", { ");
                foreach (var x in itr.Value)
                    Console.Write(x + " ");
                Console.WriteLine("}");
            }
        }
    }
}

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!