This is my take on the exercises sent by subscribing to Daily Coding Problem

Today’s problem is:

Given a list of numbers, return whether any two sums to k. For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

Solution

I wrote my solution in C#:

public class TwoSum{
    public static bool Evaluate(int[] input, int k){
        bool result = false;
        var visitedValues = new Dictionary<int, int>();
        var complement = 0;
        for (var i = 0; i < input.Length; i++) {
            complement = k - input[i];
            if (visitedValues.ContainsKey(complement)) {
                //we found our pair, return true
                return true;
            }
            else {
                if (!visitedValues.ContainsKey(input[i])){
                        visitedValues.Add(input[i], i);
                }
            }
        }
        return result;
    }
}

Explanation

The basic implementation of this program would be to iterate over every entry in the list and calculate if any two pairs sums to the k amount, however comparing every object of a list of size N against all elements in the same list would result in a O((N-1) * (N - 1)) if we ignored the current element we are visiting, which is almost equivalent to O(N^2) comparison in a worst case scenario, as the problem never stated that the list was ordered (Insight: it would help clarify this and come up with a solution that would take advantage of this). Think of a list of only 3 elements [4, 3, 10] and k = 13. We would calculate the sum of 3 + 10 until the one-to-last iteration. It would go something like this:

  • 4 + 3 = 7
  • 4 + 10 = 14
  • Iterate over the next element:
  • 3 + 4 = 7
  • 3 + 10 = 13 –> Bingo!

We did 4 comparisons before we came up with the answer. If k was a different value that was not achievable it would get worst as we would iterate over each element N - 1 times as described before.

We can do better than that.

If we know the target value (k) then we can store the previous values on a different structure, after all, we were not told that there was a memory constraint, only that we try to achieve this in one pass. It would obviously can get messy as we would now use potentially O(N) memory to calculate it, but the tradeoff is worth it as we can calculate the result in O(N) time!

When we pass over each element, we can:

  1. Calculate how much do we need to get to the sum k (the ‘complement’ variable in my example)
  2. If the complement has not been stored before, we can store the value of the current element.
  3. If we have previously visited a value that computes to the complement, we know there are at least two values that sum to k so we can safely return true at this point.
  4. If we never run into the complement of every element in the list we can assure that there was no 2 values in the list that sum k and return false.

The trick here is using a data structure that allows to check for stored values and do this in constant time O(1). A hashmap, or in the case of .Net a Dictionary, is a structure designed just for this, where we can look up values and the time to search for them is theoretically O(1). I’d invite you to review the actual implementation of the .Net Dictionary<TKey, TValue> class class as it is really interesting.

That’s all for today! Hope you have learned something cool today and remember to always read the problem twice before attempting to solve and don’t rush to code solutions without having a good understanding of what is actually being asked.

Na lû e-govaned ‘wîn