451. Find the sum of overlapping elements in two sets

Objective: Given two sets of integers, write an algorithm to print the sum of overlapping elements in two sets.

Note: Elements in each set are unique or there are no duplicates within a set.

Example:

Set 1: [2, 3, 1, 6]
Set 2: [4, 0, 6, 7]
Sum of overlapping elements: 12
Explanation: Common element is 6

Set 1: [12, 13, 6, 10]
Set 2: [13, 10, 16, 15]
Sum of overlapping elements: 46
Explanation: Common elements are 10, 13

Naive Approach: Brute force

Initialize sum = 0. Use nested for loops to compare each element with one set with another and whenever there is a match add both to sum. At the end print the sum.

Time Complexity: O(N2)

Better Approach: Use Map

• Create a map.
• Insert all the elements from both the sets with the element as key and its count (in both arrays).
• Now iterate through constructed map and sum all the elements with count=2.

Time Complexity: O(N), Space Complexity: O(N)

Output:

Set 1: [2, 3, 1, 6], Set 2: [4, 0, 6, 7]
Sum of overlapping elements: 12
----------------------------------------
Set 1: [12, 13, 6, 10], Set 2: [13, 10, 16, 15]
Sum of overlapping elements: 46