The Pair Finding Problem

In the Arrays section, you solved two-sum on a sorted array using two pointers. But what if the array isn't sorted?

You could sort it first ($O(n \log n)$), but that changes indices. What if you need the original indices? Hash maps solve this in $O(n)$ without sorting. The idea: for each element $x$, check if $target - x$ exists.