I think to achieve O(n) we need to use a hashtable.
1
Sigiloso
13 de nov. de 2013
1. Load the items of the array A into a HashSet S. Each insert will take amortized O(1) time.
2. Iterate through the integers of array B and check if the HashSet contains the integer. Each lookup also takes O(1) time.
So the overall algorithm is O(n) time.