During a phone interview for a Software Development Engineer position in Amazon I was asked to find, and code via the CollabEdit platform, the solution to the following problem:

** Given an array of integers, write a method that returns true if in the array there are two elements that added together give the value X provided as input and false otherwise.**.

Let’s see how to deal with the problem.

The first idea is to use a brute force strategy and to add together all the pairs of values and comparing the result with the value X given as input.

The image below illustrates the procedure, which is to start from the first element and at each iteration add it to the following ones, then return to the second element and repeat the operation, starting with the next one. The comparison with the previous is not executed because it has already been done in the previous iteration. In the image are marked with a dashed red line the comparisons that are not performed.

Let’s implement this first solution:

public class AmazonSumToX { public static boolean findSumBruteForce(int[]a, int x) { for (int i=0; i< (a.length-1); i++) { for (int k=i+1; k < a.length; k++) { if((a[i] + a[k]) == x){ System.out.println(a[i] + " + " + a[k] + " = " + x); return true; } } } return false; } public static void main(String[] args) { // inputs int[] ar = { 10, 5, 6, 20, 12, 40, 11, 3, 25, 15, 14, 1 }; int x = 55; boolean ris = findSumBruteForce(ar, x); System.out.println("Found: " + ris); } }

So we created our method, and we provide it in input an array of integers and a value x to search for. With the test case provided, we expect that the function returns true, because there is the pair of elements 40 and 15 that sums to our x 55.

Running the program we get the following result:

40 + 15 = 55 Found: true

Now submit to the program a test case in which we assign to the x variable a value that is not obtained from the sum of any of the pairs of elements present.

We modify in the code the line above:

int x = 100;

and we get:

Found: false

At this point we analyze the complexity of the algorithm in terms of the number of comparisons between the pairs of elements.

The first element is compared with all the other elements so, for an array of length N, the first element is compared N-1 times. The second element, is compared with all elements except the first and itself, so it performs N-2 comparisons. The third element N-3 comparisons and so on, until the second to last element that performs just one comparison with the last element.

We now analyze the **worst case**, the one in which there aren't two elements whose sum is equal to the input x value. In this case the algorithm performs ** (N-1) + (N-2) + (N-3) ... + 1 ** comparisons and we can calculate this number as ** (N * (N-1))/2 **

Let's go back to our example and modify the code by adding a variable for comparisons counting that will be printed to video at the end of the function:

public class AmazonSumToX { public static boolean findSumBruteForce(int[]a, int x) { int count = 0; for (int i=0; i< (a.length-1); i++) { for (int k=i+1; k < a.length; k++) { count++; if((a[i] + a[k]) == x){ System.out.println(a[i] + " + " + a[k] + " = " + x); System.out.println("Number of comparisons: " + count); return true; } } } System.out.println("Number of comparisons: " + count); return false; } public static void main(String[] args) { // inputs int[] ar = { 10, 5, 6, 20, 12, 40, 11, 3, 25, 15, 14, 1 }; int x = 55; boolean ris = findSumBruteForce(ar, x); System.out.println("Found: " + ris); } }

By running this new version of the program we get:

40 + 15 = 55 Number of comparisons: 49 Found: true

If we change again our x assigning it a value that does not appear as a sum of two elements in the array, we get:

Number of comparisons: 66 Found: false

The number of comparisons obtained in the worst case is 66 given as seen above by:

N = 12

N-1 = 11

(N * (N-1))/2 = 132/2 = 66

Obviously this solution is not very efficient, so we have to find a way to produce the same result but with a lower computational complexity.

One way to do it, and it is the solution with I came up during the interview, is the following:

- Sort the array using an efficient algorithm as the QuickSort (average case O (n * logn))
- Sum the first and the last element, maintaining two indexes on them and then:
- Return true if their sum is equal to x
- Increase the index of the lower element if the sum is less than x
- Decrement instead the index of the higher element if the sum is greater than x

The following figure shows an example of this process: we have an array of elements and the input x value to search for is equal to 14.

The first step is to sort the array. Once that is done, as said before, we assign two indexes on the first and last element and we start the comparisons to these two elements. In this case the first element is 3 and the last is 20 so we get 23 as sum that is greater than our target 14. For this reason we decrement the higher index to the previous position and we sum this time the element 3 to the element 15. The result is still greater than 14 so we have to decrement again the higher index that will point to the element 10. Summing 3 e 10 we get 13 that is now lower than 14 and this time we keep fixed the higher index and we increase the lower index. Then we add the element 5 and element 10, getting 15 and then we decrement the higher index. This time adding elements 5 and 9 we get the target value 14, so we have completed the search.

Let's implement this new version of the function:

import java.util.Arrays; public class AmazonSumToX { public static boolean findSumSort(int[] a, int x) { Arrays.sort(a); // quicksort for (int i = 0, k = a.length - 1; i < k;) { int tmp = a[i] + a[k]; if (tmp == x) return true; else if (tmp < x) i++; else k--; } return false; } public static void main(String[] args) { int[] ar = { 10, 3, 5, 8, 15, 9, 20 }; int x = 14; boolean ris = findSumSort(ar, x); System.out.println("Found: " + ris); } }

Now we can provide to our method the array and the value of input used in the example shown before, and try to run it. Before to do that, we add some print statement that will allow us to trace the flow of execution, and the sequence of comparisons performed by the algorithm:

public static boolean findSumSort(int[] a, int x) { Arrays.sort(a); // quicksort for (int i = 0, k = a.length - 1; i < k;) { int tmp = a[i] + a[k]; System.out.println(a[i] + " + " + a[k] + " = " + tmp); if (tmp == x) return true; else if (tmp < x) { System.out.println(tmp + " < " + x); i++; } else { System.out.println(tmp + " > " + x); k--; } } return false; }

Running the program the output we get is:

3 + 20 = 23 23 > 14 3 + 15 = 18 18 > 14 3 + 10 = 13 13 < 14 5 + 10 = 15 15 > 14 5 + 9 = 14 Found: true

The output reflects the sequence of operations described above by the figure.

As usual, we try it on a test case where the value of x is not present within the input array. We assign such as x = 16 and we get:

3 + 20 = 23 23 > 16 3 + 15 = 18 18 > 16 3 + 10 = 13 13 < 16 5 + 10 = 15 15 < 16 8 + 10 = 18 18 > 16 8 + 9 = 17 17 > 16 Found: false

The worst case is always the one in which a pair of elements that sum to x is not present and in this case the complexity of the algorithm is given by:

** the cost of the sorting process (n * logn) + (n-1) comparisons between the elements**

Now we perform a comparison on the behavior of the two algorithms in terms of performance in the worst case, at the increasing of the size N of the input array.

We modify the code in the following way, where each time we populate an array with random numbers lower than 100 and we provide as input an x value that can not be reached by the sum of two elements of the array.

import java.util.Arrays; import java.util.Random; public class AmazonSumToX { public static final int NUM_OF_ELEMENTS = 50_000; public static boolean findSumSort(int[] a, int x) { Arrays.sort(a); // quicksort for (int i = 0, k = a.length - 1; i < k;) { int tmp = a[i] + a[k]; if (tmp == x) return true; else if (tmp < x) i++; else k--; } return false; } public static boolean findSumBruteForce(int[]a, int x) { for (int i=0; i< (a.length-1); i++) { for (int k=i+1; k < a.length; k++) { if((a[i] + a[k]) == x) return true; } } return false; } public static void main(String[] args) { int[] ar = new int[NUM_OF_ELEMENTS]; int x = 210; Random r = new Random(); for (int i =0; i < NUM_OF_ELEMENTS; i++) ar[i] = r.nextInt(100); System.out.println("Array SIZE: " + NUM_OF_ELEMENTS); long startTime = System.nanoTime(); boolean ris = findSumBruteForce(ar, x); long endTime = System.nanoTime(); System.out.println("Brute Force: " + ris + " - Time: " + ((endTime-startTime)/1000000.0)); startTime = System.nanoTime(); ris = findSumSort(ar, x); endTime = System.nanoTime(); System.out.println("Sort and Search: " + ris + " - Time: " + ((endTime-startTime)/1000000.0)); } }

The following are the significant results of the repeated executions of two algorithms on an input array of size from 50 thousand to 500 thousand items. Values are expressed in milliseconds.

**As we can see the second solution offers significantly better performance!**

Array SIZE: 50000 Brute Force: false - Time: 1344.479255 Sort and Search: false - Time: 4.626856 Array SIZE: 100000 Brute Force: false - Time: 5360.940353 Sort and Search: false - Time: 5.980064 Array SIZE: 200000 Brute Force: false - Time: 21429.703085 Sort and Search: false - Time: 9.089177 Array SIZE: 500000 Brute Force: false - Time: 134992.31612 Sort and Search: false - Time: 20.261945

The source code of the example program is available for download here:

Pingback: Amazon Interview: find the only element that appears an odd number of times within an array of integers | Dede Blog

Awesome explanation… This is what I was looking for

I’m really happy it helps you. Thank you for your feedback!

Great explanation. Kudos to you. Thank you for helping me understand such problems. Were you hired at Amazon? If you did, can you please guide me through as I will be having interview with them soon? Thanks!!

Awesome. This is how CS courses should be taught!

Very nicely laid out post detailing complexity and cost! Thank you!

Hi Davis, Thanks for this post. Just wanted to point out that there is an even more efficient solution that runs in linear time (O(n)), using hash maps.