# Find Pair With Given Sum in Array

As I’m moving more and more into management I need ways to keep my coding foo fresh so I have taken to solving small problems from various sites on the internet in my spare time. I also miss that feeling of being in the zone and fully engaged in something just difficult enough to stretch myself.

After finding a problem I first attempt the problem without resorting to Google which normaly results in a very naive approach but prepares my mind for learning a better solution. I then revisit the approach and try to improve it by myself, after I have exhausted this I then find ways to improve it from the internet and then implement the Benjamin Franklin Method in order to learn more effectively and prevent just copying and pasting the solution. I then blog about it because the act of writing helps solidify the learning process and clarifys my thoughts.

## Problem

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

For example

Input:

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

Output:

``````Pair found (8 + 2)
``````

### First Attempt

``````int[] listOfInts = new int[] { 8, 7, 2, 5, 3, 1 };
for (int i = 0; i < listOfInts.Length; i++)
{
for (int k = 0; k < listOfInts.Length; k++)
{
if (i != k && listOfInts[i] + listOfInts[k] == 10)
{
Console.WriteLine("Pair found ({0} + {1})", listOfInts[i], listOfInts[k]);
return;
}
}
}
``````

The problem with this solution is we are taking a brute force approach by looping through the array twice O(n2) and the space used by the program is O(1).

### Second Attempt - Divide and Conquer

If we sort the array and then have two indices at the high and low points we can maintain a search space that allows us to reduce the work needed on each iteration O(n log n) and the space used by the program is O(1).

``````int[] listOfInts = new int[] { 8, 7, 2, 5, 3, 1 };
Array.Sort(listOfInts);
var low = 0;
var high = listOfInts.Length - 1;
for (int i = 0; i < listOfInts.Length; i++)
{
if (listOfInts[low] + listOfInts[high] == 10)
{
Console.WriteLine("Pair found ({0} + {1})", listOfInts[low], listOfInts[high]);
return;
}
if (listOfInts[low] + listOfInts[high] < 10)
{
low++;
}
else
{
high--;
}
}
Console.WriteLine("No pair found");
`````` 