Practice-It

Write a method union that accepts two maps (whose keys and values are both integers) as parameters, and returns a new map that represents a merged union of the two original maps. For example, if two maps m1 and m2 contain these pairs:

{7=1, 18=5, 42=3, 76=10, 98=2, 234=50}     m1
{7=2, 11=9, 42=-12, 98=4, 234=0, 9999=3}   m2

The call of union(m1, m2) should return a map that contains the following pairs:

{7=3, 11=9, 18=5, 42=-9, 76=10, 98=6, 234=50, 999=3}

For the purposes of this problem, we will define the "union" of two maps m1 and m2 as a new map that contains every key from m1 and every key from m2. Each value stored in your "union" map should be the sum of the corresponding value(s) for that key in m1 and m2, or if the key exists in only one of the two maps, that map's corresponding value should be used. For example, in the maps above, the key 98 exists in both maps, so the result contains the sum of its values from the two maps, 2 + 4 = 6. The key 9999 exists in only one of the two maps, so its sole value of 3 is stored as its value in the result map.

You may assume that the maps passed are not null, though either map (or both) could be empty. Though the pairs are shown in sorted order by key above, you should not assume that the maps passed to you store their keys in any particular order, and the map you return does not need to store its keys in any particular order.

You may create one collection of your choice as auxiliary storage to solve this problem. You can have as many simple variables as you like. You should not modify the contents of the maps passed to your method. For full credit your code must run in less than O(n²) time where n is the combined number of pairs in the two maps.