# 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.

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