Finding pairs of numbers within A that add up to N

I am working on an interview question from Amazon Software Interview:

Given an integer N and an array of unsorted integers A find all pairs of numbers within A which add up to N

I have a working solution in Java:

static void allPairsAddToN(int[] array, int n) {
for(int c=0;c<array.length; c ++) {
for(int j=c+1; j<array.length; j++) {
if(array[c] + array[j] == n)
System.out.println("(" + array[c] +", " + array[j] +")" );
}
}
}


Is this the most efficient solution? To me, this is the brute force approach that runs in $O(n^2)$. But for this problem, wouldn't you have to try every possibility (unsorted)? Is there some trick where you don't?

If you had a sorted array of n numbers, then finding pairs that sum to N should take O(n) time.

Sorting should take O(n log n) time.

O(n log n + n) is O(n log n). That's better than O(n2). Therefore, you would be better off sorting the array first.

• I mean if had something sorted like {1,2,3,4,5} and you were trying to find sum to 8, wouldn't it still be $O(n^2)$ because you have to start from 1, 2, etc and check all combinations? Commented Mar 2, 2015 at 5:25
• Think about how you would take advantage of the fact that the numbers are sorted. Commented Mar 2, 2015 at 5:39
• @committedandroider First thing you can do if the array is sorted is to exclude the elements greater than N (if only unsigned values are permitted). And to reduce the complexity to O(n log n) you can use binary search to find the second number in the list. Commented Mar 2, 2015 at 13:11
• @MarcDefiant why would you use binary search? That's only if you were trying to find a value in the array, not a value that would add to a sum with another number Commented Mar 2, 2015 at 19:04
• Yes, that is how you could use binary search. Yes, the two pointers approach would be better. Commented Mar 2, 2015 at 19:13

If depends what you mean by "find". Here's one option, if you just want to count the pairs and you don't mind using extra memory.

Create an empty hash map of integers to integers. This will store how many occurrences of each number we've seen.

For each element $x$ in the array, use the map to check how many times we've seen $N - x$. Then increment the number of occurrences of $x$ in the map.

Since querying and insertion are usually $O(1)$, this will usually run in $O(n)$ time, where $n$ is the length of the array.

If instead of just counting, you want to enumerate the pairs (e.g. print them), then the worst case will be when every pair sums to $N$. For example, the array is $\{ x, x, x, \ldots, x \}$ and $N = 2x$.

If the array has length $n$, then there are $\binom n2 = \frac{n(n - 1)}{2} = O(n^2)$ pairs, so any algorithm that enumerates them will have to take at least $O(n^2)$ time in the worst case.

• In that thread, Jon Skeet said that "In the worst case, a HashMap has an O(n) lookup", So wouldn't for each x in the array see how many times we've seen N-x" run in O($n^2$)? And that be the runtime as the brute force approach I proposed. Commented Mar 2, 2015 at 19:18
• @committedandroider that's correct, but the worst case is very unlikely, so you can in practice treat is as an $O(1)$ operation. See also this thread and Wikipedia. Commented Mar 2, 2015 at 20:25