Find pair with given sum in the array

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

 

For example,


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

Download   Run Code

Java

Download   Run Code



Output:

Pair found at index 0 and 2

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1).
 


 

2. O(nlogn) solution using Sorting –

 

The idea is to sort the given array in ascending order and maintain search space by maintaining two indexes (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++

Download   Run Code

Java

Download   Run Code



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++

Download   Run Code

Java

Download   Run Code



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: Print all pairs in the array having given sum

 
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

Notify of
avatar
Sort by:   newest | oldest | most voted
AllergicToBitches
AllergicToBitches

Awesome post..

Sidd
Sidd

When you sort it, don’t you change where the indexes are? How do you account for that and still output the original indexes if you try to solve this problem with the sorting method?

anonymous
anonymous

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.

nick
nick

slight correction, you said a correct output to the inputs

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

was

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

when the actual index of 3 was 4.

wpDiscuz