Given an unsorted array of integers, find a pair with given sum in it.

**Input:**

arr = [8, 7, 2, 5, 3, 1]

sum = 10

**Output:**

Pair found at index 0 and 2 (8 + 2)

or

Pair found at index 1 and 4 (7 + 3)

### 1. Naive Approach –

Naive solution would be to consider every pair in given array and return if desired sum is found.

## C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <stdio.h> // Naive method to find a pair in an array with given sum void findPair(int arr[], int n, int sum) { // consider each element except last element for (int i = 0; i < n - 1; i++) { // start from i'th element till last element for (int j = i + 1; j < n; j++) { // if desired sum is found, print it and return if (arr[i] + arr[j] == sum) { printf("Pair found at index %d and %d", i, j); return; } } } // No pair with given sum exists in the array printf("Pair not found"); } // Find pair with given sum in the array int main() { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class FindPair { // Naive method to find a pair in an array with given sum public static void findPair(int[] A, int sum) { // consider each element except last element for (int i = 0; i < A.length - 1; i++) { // start from i'th element till last element for (int j = i + 1; j < A.length; j++) { // if desired sum is found, print it and return if (A[i] + A[j] == sum) { System.out.println("Pair found at index " + i + " and " + j); return; } } } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int A[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(A, sum); } } |

`Output:`Pair found at index 0 and 2

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(1).

### 2. O(nlog(n)) solution using Sorting –

The idea is to sort the given array in ascending order and maintain search space by maintaining two indices (low and high) that initially points to two end-points of the array. Then we loop till low is less than high index and reduce search space arr[low..high] at each iteration of the loop. We compare sum of elements present at index low and high with desired sum and increment low if sum is less than the desired sum else we decrement high is sum is more than the desired sum. Finally, we return if pair found in the array.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <algorithm> // Function to find a pair in an array with given sum using Sorting void findPair(int arr[], int n, int sum) { // sort the array in ascending order std::sort(arr, arr + n); // maintain two indices pointing to end-points of the array int low = 0; int high = n - 1; // reduce search space arr[low..high] at each iteration of the loop // loop till low is less than high while (low < high) { // sum found if (arr[low] + arr[high] == sum) { std::cout << "Pair found"; return; } // increment low index if total is less than the desired sum // decrement high index is total is more than the sum (arr[low] + arr[high] < sum)? low++: high--; } // No pair with given sum exists in the array std::cout << "Pair not found"; } // Find pair with given sum in the array int main() { int arr[] = { 8, 7, 2, 5, 3, 1}; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.Arrays; class FindPair { // Naive method to find a pair in an array with given sum public static void findPair(int[] A, int sum) { // sort the array in ascending order Arrays.sort(A); // maintain two indices pointing to end-points of the array int low = 0; int high = A.length - 1; // reduce search space arr[low..high] at each iteration of the loop // loop till low is less than high while (low < high) { // sum found if (A[low] + A[high] == sum) { System.out.println("Pair found"); return; } // increment low index if total is less than the desired sum // decrement high index is total is more than the sum if (A[low] + A[high] < sum) { low++; } else{ high--; } } // No pair with given sum exists in the array System.out.println("Pair not found"); } // Find pair with given sum in the array public static void main (String[] args) { int[] A = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(A, sum); } } |

`Output:`Pair found

The time complexity of above solution is O(nlogn^{}) and auxiliary space used by the program is O(1).

### 3. O(n) solution using Hashing –

We can use map to easily solve this problem in linear time. The idea is to insert each element of the array arr[i] in a map. We also checks if difference (arr[i], sum-arr[i]) already exists in the map or not. If the difference is seen before, we print the pair and return.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <unordered_map> // Function to find a pair in an array with given sum using Hashing void findPair(int arr[], int n, int sum) { // create an empty map std::unordered_map<int, int> map; // do for each element for (int i = 0; i < n; i++) { // check if pair (arr[i], sum-arr[i]) exists // if difference is seen before, print the pair if (map.find(sum - arr[i]) != map.end()) { std::cout << "Pair found at index " << map[sum - arr[i]] << " and " << i; return; } // store index of current element in the map map[arr[i]] = i; } // we reach here if pair is not found std::cout << "Pair not found"; } // Find pair with given sum in the array int main() { int arr[] = { 8, 7, 2, 5, 3, 1}; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
import java.util.HashMap; import java.util.Map; class FindPair { // Naive method to find a pair in an array with given sum public static void findPair(int[] A, int sum) { // create an empty Hash Map Map<Integer, Integer> map = new HashMap<>(); // do for each element for (int i = 0; i < A.length; i++) { // check if pair (arr[i], sum-arr[i]) exists // if difference is seen before, print the pair if (map.containsKey(sum - A[i])) { System.out.println("Pair found at index " + map.get(sum - A[i]) + " and " + i); return; } // store index of current element in the map map.put(A[i], i); } // No pair with given sum exists in the array System.out.println("Pair not found"); } // Find pair with given sum in the array public static void main (String[] args) { int[] A = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(A, sum); } } |

`Output:`Pair found at index 0 and 2

The time complexity of above solution is O(n^{}) and auxiliary space used by the program is O(n^{}).

**Exercise:**

1. Extend the solution to print all pairs in the array having given sum.

2. Find a pair with given sum in a BST

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

I disabled adblock on this site. The ads on this site are not at all annoying, and this is the least I can do to support the team of techiedelight. You are doing a great job. Keep at it.

Please keep up the good work. The list of problems are really appreciable. And it is easy to understand. I am going to recommend this site to my friends. Please add more problems. Please!

Awesome post..

It’s worth noting that hash table operations are O(1) on average, but O(n) in the worst case. So in the worst case, the complexity of the hash based solution is O(n^2). In practice of course, if your hash function isn’t terrible, this is still probably the fastest solution of the three.

One note though, is that the Map solution does not take into account any duplicate values.

actually it does. if you have a list {6, 10, 2, 5, 5, 3, 1}

the map you make would look like this:

[0, (10 – 6) = 4]

[1, (10 – 10) = 0]

[2, (10 – 2) = 8]

[3, (10 – 5) = 5]

[4, (10 – 5) = 5] ———> at this point it would look for a 5 in the map created so far. It would find that there is a 5 at index 3. Therefore, it would report index 3 and index 4 which is the correct output.

{8, 7, 2, 2, 3, 1} !?

Given technique works fine even for duplicates.

Here are are the last two algorithms in C (using glib for the 3rd one): https://ideone.com/1PHYH3

last algo doesnt account for the index

isPairPresent : http://ideone.com/IyXytR

In all of the code samples here, you return after the first pair is found, without checking for any other pairs out there. This way you skip the second pair in a give input.

In the hashing solution, what is the purpose of storing the index of the current element in the Map (line 26 in Java)?

Hey, thank you for sharing your concerns. Here, element is the key and its index in the array is the value. If you take another look, it is used to print the index of first element in the found pair at line 21. Hope this cleared things up.

how third solution is o(n)?

searching in map is not always o(1).

Hash table complexity analysis is usually done on the average case, which is

O(1)including collisions. Worst caseO(n)practically never happens for any dependable hash table implementation likestd::unordered_mapin C++ andHashMapin Java. It is safe to go withO(1)as hash lookups hasO(1)access with high probability. But if you’re usingstd::maporTreeMap(which are implemented using a tree), then it is a whole different story.Thank you for the solutions. I just have one question. Given the fact that the sorting is done outside the loop for the second solution, is O(nlogn) the correct time complexity?

Thank you for sharing your concerns. The time taken by the

std::sortorArrays.sortfunction would beO(nlog(n)). If the sorting procedure was written inside the for-loop, time taken would have beenO(n. Hope you’re clear now.^{2}log(n))Thank you for the clarification 🙂

i have a question. how would this handle a repeated number that is a pair? say 5,5 for 10 with first 5 at index 1 and second 5 at index 6?

Hey unordered maps and maps have unique key so use multimap….

I know the post didn’t cover this in javascript, but I ran all three of these in JS and also tested the time for the functions to run at a large scale, and the first answer was much faster.

The results of 2nd and 3rd are nearly the same. I guess JS Maps are not nearly as good as JAVA maps. Here are the JAVA results just in case you are wondering using a micro timer method.

/* results

findPair(): 6048539276 ns

findPairTwo(): 5277386525 ns

findPairThree(): 4845864175 ns

*/

And the code on GitHub in case you need to see it for some reason… https://github.com/BrianARuff/pairWithSumInArray-JAVA

has any one tried getting all the pairs in the given array ?

remove return inside if loop ….

simple solution

Hi,

Do you know 2nd method of yours won’t work if there are duplicate elements in array or if all the elements in the array are same,then there would be certain value of permutations which should be taken care of.You need to have some provision for that

Code works fine. Did you ran the code? Do you have any input on which it fails?