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

O(N logN)

First approach: PANIC

Second approach: ok let’s see… oh yeah! 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:

public int findKComplementary(int[] A, int K) { int count = 0; for(int i = 0; i < A.length; i++) { for (int j = i; j < A.length; j++ ) { if (A[ i ] + A[ j ] == K ) { if ( i != j ) count += 2; else count++; } } } return count; }

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 **HashMap**‘s **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.

public int findKComplLinearTimeLinearSpace(int[] arr, int K) { int count = 0; // Let's store every item in a hashmap, key is the array element // value is the number of time the value occurs in the array HashMap<Integer, Integer> occurrencies = new HashMap<Integer, Integer>(); // Time: O(N) // HashMap has constant access time for (int i : arr) { if (occurrencies.get(i) == null) occurrencies.put(i, 1); else occurrencies.put(i, occurrencies.get(i) + 1); } // Now let's traverse the hashmap and find out if for each key // one or more complementary values exists in the HashMap // Time: O(N) Set<Integer> keys = occurrencies.keySet(); for (Integer key : keys) { int needed = K - key; if (occurrencies.containsKey(needed)) { count += occurrencies.get(key) * occurrencies.get(needed); } } return count; }

Please note that this implementation still has a 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 ðŸ™‚

Reblogged this on jozvison.

Hi Francesco,

Hash map search operation has O(n) worst case comlexity. So your implementation has still O(n^2) complexity (worst case).

You are right for the worst case scenario. I added this to the post, thanks ðŸ™‚

If your hashing function and spread is good it won’t have o(n) complexity it will have o(1) complexity.

I also got the same codility challenge a couple of days ago (and also couldn’t do better than the O(n^2) solution during the assigned time ðŸ˜¦ ). After the test, I thought of a solution that is always O(n*log(n)) even in worst case.

But the test also allowed to use O(n) space, which you are already using in your hash table. The space restriction can also be a factor for your hash table efficiency to deteriorate.

So my solution is basically to sort the input array into a look-up table. This step is O(n) space and O(n*log(n)) time using qsort. Then, for each element in the original array, look-up K-arr[i] in the table using binary search. There is a modified binary search algorithm that works with duplicates also in O(log(n)) time. Search it on Google. So for all the array elements, this step is O(n*log(n)) time.

Total time is O(n*log(n)) best, average and worst cases. No more no less!