Problem: Find all pairs

This is a simple but interesting problem, which can be easily solved with O(n²) time complexity, but it demands to reverse your logic to solve it in O(n) time.

Problem: Let’s say, there is an array arr=[1, 2, 3, 4, 6, 7, 8, 2, 5]

Now we need to find all pairs of numbers, which sum equals to 10. But you cannot produce duplicate pairs.

Solution 1: To present a naive solution one can create two loops that traverse through array trying to find all pairs that sum up to 10. Some kind of counter would be needed to make sure we don’t produce duplicates. I am not going to focus too much on this solution as is not that interesting, so I am going to present only the pseudo code for it:

for each item1 in array
    for each item2 in array
        if we use item1 and item2 first time and
          item1 + item2 equal to 10
            add pair (item1, item2) to pairs

Solution 2: To resolve it in more efficient way, let’s look at the problem in a different way. We know that we need to add two numbers to find theirs sum, but this approach is not good enough for us as we have to visit all numbers and check them explicitly. Let us reverse addition, we know that we want numbers that sum up to 10. If we take 10 as a base and subtract a known number from it, what do we get ? We get a candidate for our pair. All we need to do now is to check whether the candidate is in our array, if it is we have a match!

To make sure we track the candidates’ values and their’s numbers of occurrences we need to pre process our input array. So what we need is to push it through some kind of algorithm, which would count the number of occurrences in our array. (every programming language has its own specific approaches, but as I focus on python in this blog let’s carry on with python) Python has got a Counter module, that is similar to what multiset is in for example C++. So we pass the array though the counter, and what we get is a map that each key is a number from our array and a relevant value is a number how many times it occurred in the array. So after passing our array to the Counter we got back occurs=({1: 1, 2: 2, 3: 1, 4: 1, 6: 1, 7: 1, 8: 1, 5: 1}.

Now we need to loop through the array keep subtracting each item from 10, checking if the result is in our new map called occurs. If it is, we need to subtract 1 from the map’s value.

The only problem here is avoiding to output pair of two 5, even if only one has been found in the input array. To deal with that problem we need to provide extra check, if we didn’t go to negative value after subtracting 1 from our map’s value.

Proposed implementation in python:

import collections
arr=[1,2,3,4,6,7,8,2,5] 
occurs = collections.Counter(arr) 
pairs = {} 
for num in arr: 
    subtr = 10 - num 
    if occurs[subtr] > 0 and occurs[num] > 0: 
        occurs[subtr] -= 1 
        occurs[num] -= 1 
        if occurs[subtr] >=0 and occurs[num] >= 0: 
             pairs[subtr] = num 
print(pairs)

As we see we loop only once through the array, so the performance of this algorithm is much better than the naive solution.

Bottom line: Never settle with a naive solution. If you think you have found the best possible solution… think again.