The trivial answer would be to compare every pair, which will give a time complexity of n*(n-1). If n is relatively large, it would be better to sort the array and than "walk" elements from both sides - time complexity: n*log(n) for sorting + n for scanning. The choice of approach depends on n - for larger n algorithm with sorting will be faster.

Agree with the former answer, but everyone agrees that the 'walking' is O(n) time complexity? for me I think it's O(nlgn)