How to find two number whose sum is given number in sorted array in O(n)?

Question

public static void findNumber(int number) {
    int[] soretedArray = { 1, 5, 6, 8, 9 };
    for (int i = 0; i <= soretedArray.length; i++) {
        for (int j = i + 1; j < soretedArray.length; j++) {
            if (soretedArray[i] + soretedArray[j] == number) {
                System.out.println(soretedArray[i] + "::" + soretedArray[j]);
                return;
            }
        }
    }
}

Using this code I am able to find the number and its complexity is O(N^2) but I have to find this using O(N) complexity i.e using only one for loop or hash-map or similar in Java.

Answer 1

I remember, I was watching the official Google video about this problem. Although it is not demonstrated in java, it is explained step-by-step in different variations of the problem. You should definitely check it:

How to: Work at Google — Example Coding/Engineering Interview

Answer 2

As explained in the Google video that Alexander G is linking to, use two array indexes. Initialize one to the first element (0) and the other to the last element (sortedArray.length - 1). In a loop, check the sum of the two elements at the two indexes. If the sum is the number you were looking for, you’re done. If it’s too high, you need to find a smaller number at one of the indexes; move the right index one step to the left (since the array is sorted, this is the right way). If on the other hand, the sum you got was too low, move the left index to the right to obtain a higher first addend. When the two indexes meet, if you still haven’t found the sum you were looking for, there isn’t any. At this point you have been n - 1 times through the loop, so the algorithm runs in O(n).

We ought to first check the precondition, that the array is really sorted. This too can be done in O(n), so doing it doesn’t break any requirements.

The algorithm may need refinement if you are required to find all possible pairs of numbers that yield the desired sum rather than just one pair.

Is this answer superfluous when the video link has already said it? For one thing, my explanation is shorter, so if it suffices, you’re fine. Most importantly, if the video is removed or just moved to another URL, my answer will still be here.