Recently I had to confront myself with Codility, for those who don’t know it Codility is an online tool that provides coding challenges and it is often used by companies in the process of hiring new people when they want to test people’s coding skills.
But that’s not all, Codility also provides a great training section where you can confront yourself with a ton of coding challenges and improve your understanding of algorithms and your problem solving skills.
Yes, someone was testing my coding skills.
One of the tests I had to solve involved the concept on “K complementary pairs” in an array, basically what I was requested to do was something like this:
Given an integer array A find all the complementary pairs in A that sums up to a provided value K, so for example given the array [2, 5, -1, 6, 10, -2] and an integer K = 4 the result must be 5 because the input array contains [2, 2] [5, -1] [-1, 5] [6, -2] [-2, 6]
The solution is expected to run with a total time complexity of
First approach that comes to mind, let’s write two nested for loops, sum up each element with each other and count how many times we get the input value K:
This works! Oh wait… it is not an O(N logN), this approach runs in quadratic time or something like that… shit.
This is the solution that I submitted however, because I had other tests to do and a limited amount of time so since I could not think of a better solution at the moment I just sent this one, better slower than nothing at all.
But then a few hours later I had the right idea, and I came up with an algorithm that solves the same problem in linear time.
The idea is the following:
Let’s use an
HashMap to store the occurrences of each item in the input array, so each entry will be (key=item, value=occurrencies).
Now traverse the
keySet() and using the input value K find out which value we need in order to produce K starting from the current item.
At this point just multiply the occurrences of the current key by the number of the occurrences of the required value.
And that’s it, here’s the code.
Please note that this implementation still has a (very) worst case time complexity which is bound to the internal implementation of the HashMap, as Alexey suggested in the comment:
Hash map search operation has O(n) worst case complexity. So your implementation has still O(n^2) complexity (worst case)
Thanks Alexey for spotting this 🙂