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 &lt; end){
            int sum = sorted[beg] + sorted[end];
            if (sum &gt; x)
                end--;
            else if (sum == x){
                result[count++] = sorted[beg];
                result[count++] = sorted[end];
                end--; beg++;
            }
            else if (sum &lt; x)
                beg++;
        }
    }


Looking for code review optimizations and best practices.
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 &gt; x)
    // ...
else if (sum == x){
    // ...
}
else if (sum &lt; 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