Finding pair of sum in sorted array

In a sorted array, I am trying to find pairs that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I believe my code is O(n). If there are other method for finding pairs the sum up to a certain value that is much more efficient, I am open to these methods!

static int[] intArray = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

public static ArrayList pairSum(int[] j, int sum) {
    int len = j.length;
    int pointer1;
    int pointer2;
    ArrayList storage = new ArrayList();

    for (int i = 0; i = 0; k--) {
            pointer2 = j[k];
            if (pointer1 + pointer2 == sum && pointer1 != pointer2) {
                i++;
                String pair = Integer.toString(pointer1) + " and " + Integer.toString(pointer2) ;
                storage.add(pair);
            }
        }
    }
    return storage;
}

If I ran this code, say pairSum(intArray,16), I would get:

[0 and 16, 2 and 14, 4 and 12, 6 and 10, 9 and 7, 11 and 5, 13 and 3, 15 and 1]

If I remove the i++, the output would be:

[0 and 16, 1 and 15, 2 and 14, 3 and 13, 4 and 12, 5 and 11, 6 and 10, 7 and 9, 9 and 7, 10 and 6, 11 and 5, 12 and 4, 13 and 3, 14 and 2, 15 and 1, 16 and 0]

EDIT: Please see update at end because there is an improved solution that is inspired by Mike Chamberlain's answer...

There are two solutions which come to mind for your problem, but first, let's look through your code:

• you have the variables pointer1 and pointer2. These are very descriptive names, which is great, but unfortunately they are not pointers. They are the values at the i and k positions in the array. In other words, i and k are the actual pointers. I would call pointer1 and pointer2 something like val1 and val2. But, in fact, I would drop the pointers entirely, and just use an index in to the data (why copy the data when you don't need to....? )

• In most languages the variable name i is 'reserved' for indexed looping through data, just like you have for (int i = 0; i






• as a general rule, when you have a loop constrained by an index, like you have for (int i = 0; i

• Your method should return the interface type List instead of the concrete class ArrayList since there is no reason for outsiders to know the physical implementation.

• storage is not a great name for a variable.... everything could be called storage since all variables store things... I would choose something like: results.

• Your inner if condition makes sure that the sums are a match, but also checks pointer1 != pointer2. This second check is a problem, because it should not be testing the values, but the indexes.... For example what if the data is [4,4] and the target sum is 8?

• To get your result pair as a String you do: String pair = Integer.toString(pointer1) + " and " + Integer.toString(pointer2).... this is serious overkill, try this instead: String pair = pointer1 + " and " + pointer2. In Java the + String operator will implicitly convert the integers to a String... no need to do it yourself.

So, you have some style problems, and some concerns about your inner workings.

Now, let's talk about your algorithm..... It loops through each value. For each value, it then compares it against every other value (except itself). So, you loop n times, and, for each n you do m checks. Your complexity is O(n x m), but, in reality, n and m are the same, so your complexity is O(n2)

Now, about that i++ inside the k loop.... the reason you need it is because your k loop is starting from the wrong place. your algorithm is wrong. Let me explain.

If you have the data [ 0, 1, 2, 3, 4, 5 ] , you are using your i index to loop through all the data. Your first data will be 0. You sum this with 5 (Note, you have summed 0 + 5 now), and check the result, then with 4, and so on. When you are done, you move i to the value 1, and you keep moving i until you get to the value 5 for i. You then compare this value 5 to all the other values, including 0. This is the second time you sum the items 0 + 5 (but it is now 5 + 0) **.

You need to change the algorithm to only scan those values that have not yet been scanned. The easiest way to do this is to modify your inner/nested loop. Consider your code:

for (int i = 0; i = 0; k--) {
           ...

Now, we change the inner loop as follows:

for (int i = 0; i < len; i++) {
    ....
    for (int j = i + 1; j < len; j++) {

(note, I have renamed k to be j). We start our j index at i + 1, because we don't need to sum values before i since that sum was done already when i was smaller.....

Now, our loops only calculate the sum value once for each pair of values.

Unfortunately, our complexity is still O(n2) because even though our inner loop is only testing half (on average) the values, we have not actually changed the way the algorithm scales (if you double the input data, you with quadruple the execution time).

Still, even with this algorithm change, and some variable renaming, and some bug fixing, your code will look like:

public static List pairSum(int[] data, int sum) {
    int len = data.length;
    int val1;
    int val2;
    List results = new ArrayList();

    for (int i = 0; i < len; i++) {
        val1 = data[i];
        for (int j = i + 1; j < len; j++) {
            val2 = data[j];
            if (val1 + val2 == sum) {
                String pair = val1 + " and " + val2;
                results.add(pair);
            }
        }
    }
    return results;
}

This is OK, but my preference would be to strip all the val1 variables entirely, and you can simplify some other things too. Consider the following more 'compact' code:

public static List pairSum(int[] data, int sum) {
    List results = new ArrayList();

    for (int i = 0; i < data.length; i++) {
        for (int j = i + 1; j < data.length; j++) {
            if (data[i] + data[j] == sum) {
                results.add(data[i] + " and " + data[j]);
            }
        }
    }

    return results;
}

That is what I would recommend for a simple, easy-to-read option that is O(n2). For sma

StackExchange Code Review Q#38994, answer score: 18