The solutions listed for this algo are all O(n), but this can be solved (again) with a simple O(logn) sort, or am I missing something?
So looking at this again, a solution using sort (merge sort for example) would be O(nlog(n)) which is worse than the provided O(n) answers.