implement using hash Let S and T be two arrays of m and n el

implement using hash

Let S and T be two arrays of m and n elements, respectively. Write an algorithm that finds all the common elements and stores them in an array U. Show t hat I his can he done in theta (n + m) time.

Solution

Do hash mapping( key value pair) for all the elements of the first array S then check each elements of a array T in the hash if it exist in the hash then store that element in a array U. Since we are doing hash for each elements of array S and checking each elements of a array T in hash it will take an order of O(n+m).