Well well, it has been a while since i last wrote something (a week I think?), mainly because my shoulder got dislocated last weekend, while snowboarding… but fear not, there will always be more questions to make your brain work and #mindflabergast you a little bit :P.

So how do we find pairs that equal to a specific sum in an array of ints? This is a very common interview question… The first thing that should pop up in your mind is specifications and ambiguity. Are we given any restrictions? Are we supposed to doubly print pairs (i.e. does position matter – is Pair(1,2) the same as Pair(2,1))? Are there any duplicates in our array?… This is part of your reasoning but for now we will leave this info aside and go head first into our quest to find pairs that equal to a specific sum in an array.

So let us start by thinking this through. The normally bad way to write out a method for this would be to simply go through each element per each element in the array and check their sum, which will take **O(n ^{2})**. However, as you should know by now if you have read my How to find if two Strings are anagrams – in most occasions anything that will look too easy and lazy, can be optimized.

So why don’t we try to think of alternate ways. Usually for anything that has to do with **O(n ^{2})** runtime in arrays, sorting the array might make our life easier. Remember that sorting only takes

**O(nlog(n))**and in special cases we can shave off the (log(n)), but again, that will need its own post and is not crucial since log(n) is comparably small even in big data.

After that we know that to look for a specific element in a sorted array in **log(n)** time from How to use Binary Search in an Array.

Hence with this in mind we can form the following algorithm:

- Sort the array – Time:
**O(nlog(n))**– Space:**O(1)**(Check HeapSort for more info - For each element in the sorted array do a binary search to find if there is an element = SUM – A[i]. If found print both elements. Time:
**O(nlog(n))**– Space:**O(1)**

)

Now that we wrote the algorithm let us get to your favorite part – coding ;D.

## First try at finding pairs that equal to a specific sum in an array

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public void printAllPairsEqualTo(int[] nFooBarArray, int nSum) { Arrays.sort(nFooBarArray); for (int i = nFooBarArray.length-1; i >= 0; --i) { if (isInSortedArray(nFooBarArray, nSum - nFooBarArray[i])) { System.out.println("Pair Found: " + nFooBarArray[i] + " , " + (nSum - nFooBarArray[i])); } } } public boolean isInSortedArray(int[] nFooBarArray, int nFindMe) { if (Arrays.binarySearch(nFooBarArray, nFindMe) < 0) // or you could use our own binary search from our previous post ;D { return false; } return true; } |

It wasn’t so hard was it?

Our code runs in Time: **O(nlog(n))** and Space: **O(1)**. That’s better than our initial horrible idea. Yay, so our job is done… or is it? Maybe we can refactor this even more. How about we use the fact that we know that if two items are bigger than the target, we can ignore all other items that will make our target bigger…

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public void printAllPairsEqualTo(int[] nFooBarArray, int nTargetSum) { Arrays.sort(nFooBarArray); //refactored after edit int nStartIndex = 0; int nEndIndex = nFooBarArray.length - 1; while(nStartIndex != nEndIndex) { if ((nFooBarArray[nStartIndex] + nFooBarArray[nEndIndex]) == nTargetSum) { System.out.println("Pair Found: " + nFooBarArray[nStartIndex] + " , " + nFooBarArray[nEndIndex]); ++nStartIndex; } else if ((nFooBarArray[nStartIndex] + nFooBarArray[nEndIndex]) > nTargetSum) { --nEndIndex; } else { ++nStartIndex; } } } |

Let us think again… we can usually make a Time-Space trade off using a Hash Table. Well if we put all of our values in a hash table, than we would not need to sort and instead of binary search **O(log(n))** we could just retrieve the values in **O(1)** time.

So our algorithm will be like this:

- Put each element in a HasTable with Key – ArrayElement and Value – ArrayIndex – Time:
**O(n))**– Space:**O(n)** - For each element in the array check if there is an element associated to the SUM – A[i] key in the array. If found print both elements. Time:
**O(n)**– Space:**O(1) (note that checking only takes Time:****O(1)**!

Yay, we have shaved off some more time but decreased our Space performance… So let us write the code for this too.

## Second try at finding pairs that equal to a specific sum in an array

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public void printAllPairsEqualTo(int[] nFooBarArray, int nSum) { HashMap<Integer, Integer> nFooBarHashMap = new HashMap<Integer, Integer>(nFooBarArray.length); //refactored after edit for (int i = nFooBarArray.length-1; i >= 0; --i) { if (nFooBarHashMap.containsKey(nSum - nFooBarArray[i])) { System.out.println("Pair Found: " + nFooBarArray[i] + " , " + (nSum - nFooBarArray[i])); } else { nFooBarHashMap.put(nFooBarArray[i], i); } } } |

Great! Our code runs in Time: **O(n))** and Space: **O(n)**. A lot better than our initial Time: **O(n ^{2})** idea.

There you go. Give yourself a pat in the back for reading/writing through this. By now you should know how to find pairs that equal to a specific sum in an array more time efficiently and more space efficiently. You will also have revised basic concepts of Sorting, Searching, Arrays and Hashtables on the way.

Hope you guys enjoyed it…. And I’ll see you guys next time ðŸ˜‰

Edited after feedback:

– Use 1 for loop in HashMap version

– Use two pointers that come together in the sorting version, instead of binary serach, to reduce time complexity of that part from O(nlog(n)) to O(n)

#### Latest posts by Ajk (see all)

- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017

There’s an edge case with your map version, you probably need to make use of that index you’re storing.

Consider: printAllPairsEqualTo(int[]{2}, 4)

Very good catch!

Yes I need to update this with some feedback I got:

– HashMap => Use one loop (and probably HashSet if there’s no duplicates).

– Sorting way => Use two pointers at the start and end of the array that come together, instead of binary search for each – reducing complexity from O(nlog(n)) to O(n)

Great article.

There is an error on the 2nd version.

Where:

else if ((nFooBarArray[nStartIndex] + nFooBarArray[nEndIndex]) < nTargetSum) {

–nEndIndex;

} else {

++nStartIndex;

}

Should be:

else if ((nFooBarArray[nStartIndex] + nFooBarArray[nEndIndex]) < nTargetSum) {

++nStartIndex;

} else {

–nEndIndex;

}

Good catch!

I intended to put a “>” on the first check – (nFooBarArray[nStartIndex] + nFooBarArray[nEndIndex]) > nTargetSum)

Edited ðŸ™‚

[…] we can see this is looking pretty bad. I am sure we can optimize this a lot more. Remember from our Find pairs equal to a sum problem that whenever we see a O(n2) time complexity in arrays we can always try to improve our performance […]