# Given an unordered list of numbers, find all pairs that add up to x

I am coding an interview question from Yahoo Software Engineer Intern Interview.

Given an unordered list of numbers, find all pairs that add up to x.

I have a working solution in Java:

    public static void main (String args[]){
int[] numbers = new int[]{2, 5, 7, 3, 9, 4, 1, 8}; //input array
int x = 6; //target sum

int[] result = new int[numbers.length]; //stores the output pairs
int count = 0;

int[] sorted = numbers;
Arrays.sort(sorted);
int beg = 0;
int end = numbers.length-1;
while (beg < end){
int sum = sorted[beg] + sorted[end];
if (sum > x)
end--;
else if (sum == x){
result[count++] = sorted[beg];
result[count++] = sorted[end];
end--; beg++;
}
else if (sum < x)
beg++;
}
}


Looking for code review optimizations and best practices.

Design

Your code should really be put into a function that can be called with any array of ints (Or even more ideally, a more generic container) together with the target value. This would change the code to be more in line with OO design principles and with how Java programs are usually written.

Algorithm

Your solution only works under the assumption that all the numbers are unique. If they are allowed to be non-unique, there can be up to $n^2$ valid pairs, where $n$ is the number of given numbers.

Assuming that the numbers are unique, you are wasting a lot of extra space by using a fixed size result array. In the worst case, when there are no pairs, you are still using $O(n)$ space. I would at least use an ArrayList<Integer> (A type of dynamically sized array, growing as needed in amortized constant time). Furthermore, your storage mechanism is a bit odd, as every pair is stored as two consecutive entries. I would instead use a Map<Integer, Integer> type where the key is the first number in the pair and the value is the second number.

Aside from that, your algorithm runs in $O(n\ log(n))$, which is fine, but you can be a bit more clever and get $O(n)$ performance as follows:

• Use a HashMap<Integer, Integer> to store the values in the array (as a key), and the number of times they occur (as a value). Let's call it T as a shorthand (use a more descriptive name in your code).
• Loop through all the given numbers, and fill out the previous hash table, i.e. determine if the number is in T, if so, then increment its count, otherwise add it to T with a count of 1.
• Loop through all the entries in the table, determine if TARGET_SUM - entry is in T, if so then output the pair (entry, TARGET_SUM - entry) occurs T[entry] * T[TARGET_SUM - entry] times. Note that if you decide to output each pair several times then the complexity rises to $O(n^2)$ as there could be that many pairs if there are duplicates.

This solution has the added benefit of handling duplicates.

• Very good points, especially the one about the consequences of duplicates and how to handle them elegantly. However, hash maps are O(1) only in academic papers, and only amortised. Their use in practical applications needs to be considered carefully and benchmarked, since the 'constant' factor dropped by the asymptotic can be considerable (starting with the cost of calculating the hash). Non-hash maps are even more problematic when performance matters - they start slow and get slower quickly. Mar 25, 2016 at 7:29
• @DarthGizka In the context of this problem, it is very unlikely that hash maps will encounter performance issues, especially considering typical problem scales. In this particular case, you can actually construct a hash map that exhibits guaranteed constant time performance by using a very large table size of ~4 billion (number of int's). This would take up an absurd amount of memory, and is a glorified array, but it is possible :) Mar 25, 2016 at 7:47
• Yes, that's precisely what I meant with 'needs to be considered carefully and benchmarked'. The cache performance of such a huge table would be abysmal. ;-) In general, the simplest and cleanest solution is the best, and when there are performance problems then these very same problems can serve to direct the choice for their resolution. The OP's code contains some goodness that is not readily apparent: the 'n log n'-ness is contained in the focussed act of sorting and the solver loop is tight; a map would smear the search effort (hashy or otherwise) over the solver loop and confuse the CPU. Mar 25, 2016 at 8:12
• I don't like the idea of a Map - this isn't a mapping. It seems counter-intuitive at the very least. I would expect either a Set<int[]> where the inner int[] has two values - or better a Set<Pair> where Pair is a class created for the purpose. Mar 25, 2016 at 14:27
• @BoristheSpider In C++, I would totally agree with you, but creating a one-off type just for such a simple problem is ridiculous. Mar 25, 2016 at 16:06

What is the time complexity of this solution? They will definitely ask that.

The description doesn't specify the ordering of the pairs. It would be good to ask to clarify. If the pairs can be unordered, and the numbers are unique, a more efficient algorithm exists. (Hint: would it help to use a hash set? What will be the time complexity then? If the numbers may contain duplicates, then a hash map of counts could be used, as @mleyfman pointed out.)

This looks suspicious:

int[] sorted = numbers;
Arrays.sort(sorted);


The variable sorted is redundant. You simply gave numbers another name. Which is fine, as long as you keep in mind that the sort operation destroys the original ordering of the input.

Speaking of input... You implemented the solution in a main method, using hardcoded values. It would be better to write a proper function that takes the array and target as parameters, and (ideally) return something. That way the solution becomes unit-testable.

In this if-else chain the last else if can be a simple else:

if (sum > x)
// ...
else if (sum == x){
// ...
}
else if (sum < x)
// ...


And it's recommended to use braces with even single-line statements.

With a better name for x (like target), you wouldn't need the comment here:

    int x = 6; //target sum

• The set would simply hide the n log n that's explicit in the sorting, unless it's a hashed set. I'd rate it as unnecessary complication that has to furnish proof of necessity... Mar 25, 2016 at 6:37
• @DarthGizka I edited to specify hash set instead of just set. Thanks, good point Mar 25, 2016 at 6:53
• @janos Thanks for your feedback about names I used. I am working writing more readable code and these suggestions have helped me understand how I should think while deciding variable names. Mar 29, 2016 at 22:25

Your solution is clean and efficient, but it does not 'speak', it does not tell the reader what its logic is.

A simpler solution - like iterating over all input numbers k and checking whether x - k is present (set, bitset, binary search in a sorted vector, whatever) - could get away without explanations/comments, but your solution definitely needs extra prose to prove to the reader that it accomplishes what it is supposed to. Without sufficient explanation, the reader would be forced to analyse the problem, find the connection to your solution, and then verify its correctness, all in the head.

I used the word 'prove' because what's needed is similar to an excerpt from a correctness proof, telling why the last element of the current sorted list can safely be discarded when sum > x. The case sum < x (Janos has already pointed out that the test is redundant) can then simply be explained as 'mirror case to (sum > x)' or some such. I.e. you only need to supply the most significant missing bits of the logic, as mental stepping stones.

If you do this then you make your code more self-explanatory and smoother to read.

The name end is ill-fitting as it customarily refers to the first element past the current range; the last element is usually called last or back.

Pros:

• code is clean
• variables reasonably well defined

Cons:

• this should be extracted into a function
• Naming the pointers as start and end would be better
• This code somewhat looks muddy. This is contributed by how the pair is saved in the int array. Rather lets introduce a Pair class which can be defined as:

class Pair { private int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }

A good example can be found here: Return all pairs from a list of integers that contributes to a given sum