511. Sum of all the overlapping elements

Given two arrays of integers. Write a program to find the sum of all the overlapping elements between two arrays. You can consider that there will not be any duplicates in each array individually.

Example:

A [] : [6, 5, 1, 9, 2, 8, 3]
B [] : [3, 7, 9, 2, 4]
Overlapping sum of two arrays: 28
(Overlapping elements are 9, 2, 3)

A [] : [6, 5]
B [] : [3, 7]
Overlapping sum of two arrays: 0
(No overlapping elements)

Approach:

Naive Approach: Use nested loops and compare every element from one array with all the elements in another array and get the sum of overlapping elements.

Time Complexity: O(N²)

Better Approach: Use Set

Iterate through the first array and add all the elements to the HashSet. Now iterate through second array and for each element, if it is present in the set then do sum = sum + element*2. At the end return the sum.

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

Output:

A [] : [6, 5, 1, 9, 2, 8, 3]
B [] : [3, 7, 9, 2, 4]
Overlapping sum of two arrays: 28

Reference: geeksforgeeks

Related Problems:

- Number of Islands using BFS Medium
- Find no of reverse pairs in an array which is sorted in two parts in O(N) Medium
- Adding One to a Number Represented by an Array Medium
- Find two Missing Numbers in a Sequence of Consecutive Numbers Beginner
- Find Smallest Subarray Exceeding a Target Sum Medium