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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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