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:

- Sort a given stack - Using Recursion Hard
- Adding One to a Number Represented by an Array Medium
- ZigZag OR Diagonal traversal in 2d array/Matrix using queue Medium
- Get specific row K in a Pascal Triangle Medium
- Find longest Snake sequence in a given matrix Medium