From Algorithm Wiki
What about this approach?
- Create a hash entry for every value from S1[i].
- For each value in S2 look for a hash hit on x-S2[i].
Isn't that an O(n) solution?
According to the formal definition, an O(n) solution is also an O(n log n) solution, is it not?