Two-Sum With a Hash Set

For each element, check whether its complement has already been seen.

Hash set insertions and lookups take expected $O(1)$ time each.

1. 1. Describe the single-pass algorithm

   Iterate through the array once, and for each element $x$ check whether $\text{target}-x$ is already in the hash set before inserting $x$.

2. 2. Account for hash set operations

   Each of the $n$ iterations performs an expected $O(1)$ lookup and insertion, giving expected $O(n)$ total time.

Answer: Expected O(n)