# find all pairs in an array, that sum up to particular number with best complexity

March 23, 2013 7 Comments

Here we discuss two possible algorithms

- algorithm with the time complexity O(n) and with no additional space complexity
- algorithm which uses additional hashmap data structure which reduces the time complexity to O(2n) at the cost of additional space complexity O(n)
- brute force algorithm with time complexity of O(n^2)

**Algorithm with the time complexity O(n) and with no additional space complexity**

/** * Find the pair in an array whose sum with complexity O(n). This assumes * the array passed is sorted array and there are no duplicates in the array * * @param arr * input array of elements * @param k * sum for which pair of array elements needs to be searched */ public void getPair2(int[] arr, int k) { int start = 0; int end = arr.length - 1; int sum = 0; // output array to record matching pairs StringBuilder arrs = new StringBuilder(); while (start < end) { sum = arr[start] + arr[end]; if (sum == k) { // we have found one pair, add it to our output array arrs.append(arr[start] + "," + arr[end] + ";"); start++; end--; } else if (sum < k) { // if the sum of the pair is less than the sum we are searching // then increment the start pointer which would give us the sum // more than our current sum as the array is sorted start++; } else { // if the sum of the pair is greater than the sum we are searching // then decrement the end pointer which would give us the sum // less than our current sum as the array is sorted end--; } } System.out.println(arrs.toString()); }

Output: 1,5;2,4;

**Algorithm which uses additional hashmap data structure which reduces the time complexity to O(2n) at the cost of additional space complexity O(n)**

/** * Find the pair in an array whose sum with complexity O(2n) * * @param arr * input array of elements * @param k * sum for which pair of array elements needs to be searched * @return string of combination of array pairs */ public String getPair(int[] arr, int k) { HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); String result = ""; /** * First store array elements into hashmap with key as the value of the * array This has time complexity of O(n) and space complexity of O(n) */ for (int i = 0; i < arr.length; i++) { hm.put(arr[i], arr[i]); } /** * Try getting the hashmap value at key (sum-array_element) If it * exists, it means array_element and sum-array_element is the pair * thats forms sum 'k' This has time complexity of O(n) */ for (int i = 0; i < arr.length; i++) { if (hm.get(k - arr[i]) != null) { result += arr[i] + "," + (k - arr[i]) + ";"; } } return result; }

Output: Pair of elements at O(2n) time complexity and O(n) space complexity: 4,2;2,4;5,1;1,5;

**Brute force algorithm with time complexity of O(n^2)**

/** * Find the pair in an array whose sum with complexity O(n^2) * * @param arr * input array of elements * @param k * sum for which pair of array elements needs to be searched * @return string of combination of array pairs */ public String findPair(int[] arr, int k) { int i = 0, j = arr.length - 1; String result = ""; while (i < j) { while (i < j) { if (arr[i] + arr[j] == k) { result += arr[i] + "," + arr[j] + ";"; } j--; } i++; j = arr.length - 1; } return result; }

Output: Pair of elements at O(n^2) time complexity and no additional space complexity: 4,2;5,1;

Your solutions which use hashmap and brute force do not work for array = {1,2,3} and sum = 2 / sum = 4 / sum = 6

It will give you (1,1) / (1,3),(2,2) /(3,3) as solutions.

(1,1) and (2,2) cannot be solutions as those are not pairs but just single element.

Am I missing something here ?

great explanation! thank you!

If arr={0,1,2,3} and k=4, your hashmap algorithm will also return (2,2) as a pair which is not the case

adding a condition should help

if (hm.get(k – arr[i]) != null && (k – arr[i]) != arr[i])

anyways I will try it out and update the code when I get some time.

Thanks for pointing it out.

The condition check would work if its assumed that there are no duplicates.

Cell

{

int index ;//which contains the array index

int val; //which contains the array value at that index

}

u said all pairs that sum upto a given number so for array {1,2,3,4} and k=4 answer should be {1,2}, {1,3} not just {1,3}. Right ??