How to find two numbers whose sum is given in a 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 can find the number and its complexity O (N ^ 2), but I have to find it using the complexity O (N), i.e. using only one for loop or hash map or similar in Java.

Answer 1

I remember I watched the official Google video about this issue. Although this is not demonstrated in java, it is explained in stages in different versions of the problem. You should definitely check this out:

How to work at Google - Coding example / Engineering interview

Answer 2

As explained in the Google video that links Alexander G to , use two array indexes. Initialize the first element (0) and the second to the last element ( sortedArray.length - 1 ). In a loop, check the sum of two elements in two indices. If the amount is the number you were looking for, you did. If it is too high, you need to find a smaller number in one of the indices; 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 amount you received was too low, move the left pointer to the right to get a higher first addition. When the two indexes meet, if you still have not found the amount you were looking for, it is not. At this point, you ran n - 1 times through the loop, so the algorithm works in O (n).

We must first check the precondition that the array is indeed sorted. This can also be done in O (n), so doing this does not violate any requirements.

The algorithm may need to be refined if you need to find all possible pairs of numbers that give the desired amount, and not just one pair.

Is this answer redundant when video calling has already spoken about it? Firstly, my explanation is shorter, so if this is enough, you're fine. Most importantly, if the video is deleted or just moved to a different URL, my answer will still be here.

Answer 3

With a fixed number for any selected x in the array, you just need to find if number-x in the array (note that you can also bind x ). This will not give you O (n), but O (n.log (n)).

Perhaps noticing that if you have a_i and a_j ( j>i ), taking the amount and comparing with number if the result is greater, the following interesting tests are a_(i-1) or a_(j-1) , and if result below, the following interesting tests with a_(i+1) or a_(j+1) , will give a hint about linear time?