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.

You may also like...

1 Response

  1. Brent says:

    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

Leave a Reply

Your email address will not be published. Required fields are marked *