• 0

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.