Press "Enter" to skip to content

How to find pairs that equal to a specific sum in an array

Ajk 5

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(n2). 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(n2) 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:

  1. Sort the array – Time: O(nlog(n)) – Space: O(1) (Check HeapSort for more info
  2. )

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

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…

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:

  1. Put each element in a HasTable with Key – ArrayElement and Value – ArrayIndex – Time: O(n)) – Space: O(n)
  2. 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

Great! Our code runs in Time: O(n)) and Space: O(n). A lot better than our initial Time: O(n2) 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)

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂
  1. Martin L Martin L

    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)

    • Ajk_P Ajk_P

      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)

  2. Tiago Pina Tiago Pina

    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;
    }

    • Ajk_P Ajk_P

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

Leave a Reply

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