Find a pair of elements from an array whose sum equals a given number
Input:
An array of n integers and given a number X.
Expected output:
All the unique pairs of elements (a, b), whose summation is equal to X.
Example
<pre>Given<span class="pl-k">var</span> unSortedArr <span class="pl-k">=</span> [<span class="pl-c1">2</span>, <span class="pl-c1">3</span>, <span class="pl-c1">2</span>, <span class="pl-c1">5</span>, <span class="pl-c1">4</span>, <span class="pl-c1">5</span>, <span class="pl-c1">5</span>, <span class="pl-c1">5</span>, <span class="pl-c1">5</span>, <span class="pl-c1">9</span>, <span class="pl-c1">6</span>, <span class="pl-c1">8</span>, <span class="pl-c1">8</span>, <span class="pl-c1">7</span>]; sum = 10;
Because 2 + 8 = 10,
<span class="pl-c">// Pairs matching the input sum in the given array without duplicates = [ '2-8', '3-7', '4-6', '5-5' ]</span></pre>
Logic :
- Sort the given array
- Have two variables ( if you are using C then pointers ) referring to the first and last element of an array
- Store the sum of the elements referred by current two pointers in tempSum
- If tempSum === sum then add the pair as an element to an object (or Map)
- Else if tempSum > sum then decrement the end pointer by one
- Else increment the start pointer by one
Time complexity :
O ( n Log(n) + n )
Solution :
Approach 1 : Using Object data structure
Approach 2 : Using Map data structure. Map is a new data structure introduce in ES6. There is a subtle difference between these two data structures. More details doing the comparison between these two data structures can be found here.
Hi Kavit,
Thanks for the algorithm. I’ve only tried the first approach and it’s not completely waterproof. If you have the following array for example, arr = [2, 4, 8, 7, 6], the code will get stuck in a infinite loop. This happens when i = 1 and j = 2, there will be a match and both their indexes will “jump over each other” afterwards, which results in them being unable to ever match each other. Changing the code to while (i <= j) fixed it for me.
Brent