Codility tasks - Part II

Now, the second codility task I was faced with was a bit tougher. The goal was to create a function that, given a vector of integers A and an integer K, returned the number of integer pairs in the vector that, when added, sums up to K.

Let me give you an example. Assume that you are given a vector A = [0, -1, 3, 2, -5, 7] and K = 2. Possible combinations to get K are (0, 2), (-1, 3), (3, -1), (2, 0),  (-5, 7), and (7, -5). In other words, the function should return 6.

Now, how did I solve this task? The first solution that came to mind involved nested for-loops. The outer loop picking one integer at the time from the vector and the inner loop adding the integer to the others one by one to see if the result is K. This solution works, but it does not scale well. Time complexity will be O(N**2), something that for large vectors will result in very long execution times.

My second approach was to use my old friend, the integer counter, and count all occurences of each integer in the vector using the std::map. When all integers are counted a second loop can be used to count all combinations that yields K. This was the solution that I submitted, and the complexity should be O(N). But was it the optimal solution?

Well, that was what they had me believe, until they a couple of weeks after called me for an interview. Once there they wanted me to show some other, and more memory efficient solutions to the problem. I was quite surprised and couldn't come up with any other solution at the moment.

The solution they presented then was to sort the vector in ascending order, and then set two pointers, one pointing at the first element in the vector, the other pointing at the last element. Then you add the integers that the pointers point at. If the sum is less than K you increment the first pointer making it point at a larger integer. Otherwise, if the sum is bigger than K you decrement the second pointer, making it point at a smaller integer. Then you repeat the procedure and count all sums that adds up to K. It will be a bit tricky to get it right if you have several integers with the same values that adds up to K and sorting will be at least O(NlogN) or worse, depending on the sorting algorithm used.

Time for some code! This was the solution that I submitted:

int kComplement(const std::vector& A, int K)
{
  std::map<int, unsigned int> elementCounter;


  for (unsigned int i = 0; i < A.size(); ++i)
  {
    elementCounter[A[i]] += 1;
  }


  unsigned int kComplements = 0;
  for (unsigned int i = 0; i < A.size(); ++i)
  {
    kComplements += elementCounter[K - A[i]];
  }


  return kComplements;
}


Now, one source of false positives is if K is a very large negative integer, then K - A[i] might overflow. I admit this is a flaw (but easy fixed), otherwise I'm quite satisfied with the solution. It might be quite tricky to convince yourself that elementCounter[K - A[i]] will give the number of K-complements for a specific A[i]. Think like this, assume A[i] = a, we then wish to find b so that a + b = K. This is equivalent to K - a = b, but a = A[i], so K - A[i] = b. Now, putting b, or K - A[i], as index in elementCounter will give exactly the number of b's that exists in the vector. Voila!


I won't post the code for the pointer solution, since I havn't written it yet :).