How can I decrease the amount of memory and operations involved in the ""Find all the pairs that add to N" interview challenge?

Question

I was asked in an interview to write a function for finding all pairs of ints in an array that add up to N. My answer was kinda bulky:

HashSet<Tuple<int,int>> PairsThatSumToN ( int [] arr, int N )
{
    HashSet<int> arrhash = new HashShet<int> (arr);
    HashSet<Tuple<int,int>> result = new HashSet<Tuple<int,int>>();    
    for ( int i in arrhash ) 
    {
       int j = N - i;
       if ( arrhash.Contains(j) ) result.Add(new Tuple<int,int> (i,j));
    }
    return result;
}

I'm a beginner to C#, come from a C++ background, and I have a few questions about how to make this better:

• Is it innefficient to iterate through a HashSet? In other words, would my procedure be more efficient (although less compact) if I changed it to

  HashSet<Tuple<int,int>> PairsThatSumToN ( int [] arr, int N )
  {
     HashSet<int> arrhash = new HashShet<int> ();
     HashSet<Tuple<int,int>> result = new HashSet<Tuple<int,int>>();    
     for ( int i in arr ) 
     {
        int j = N - i;
        if ( arrhash.Contains(j) ) result.Add(new Type<int,int> (i,j));
        arrHash.Add(i);
     }
     return result;
  }
  

  ?????

• I realize that Add is more like an "Add if not already in there", so I have a useless operation whenever I run result.Add(new Tuple<int,int> (i,j)) for an i,j pair that is already in the set. The more repeated pairs in the array, the more useless operations, and there's all the overhead of allocating the new Tuple that may never be used. Is there a way to optimize this by checking whether the pair i,j is a Tuple in the set before creating a new Tuple out of said pair and trying to add it?

• Speaking of the above allocation of a new Tuple on the heap, do I need to free this memory if I don't end up adding that Tuple to the result? Potential memory leak here?

• There has to be some way of combining the two sets

  HashSet<int> arrhash = new HashShet<int> (arr);
  HashSet<Tuple<int,int>> result = new HashSet<Tuple<int,int>>(); 
  

  In a sense, they contain redundant information since every int in the second one is also in the first one. Something feels "wrong" about having to sets here, yet I can't think of a better way to do it.

• Better yet, does the .NET library have any way of doing a 1-line solution for the problem? ;)

Paging Dr. Skeet.

Answer 1

If you need a neat solution for your problem, here it is, implemented with LINQ.

The performance however, is 4 times worse than your second solution.

Since you have asked for a one liner, here it is anyway.

NOTE: I would appreciate any improvements especially to get rid of that Distinct() since it takes the 50% of the overall cpu time

static List<Pair> PairsThatSumToN(int[] arr, int N)
{
    return
    (
        from x in arr join y in arr on N - x equals y select new Pair(x, y)
    )
    .Distinct()
    .ToList();
}

public class Pair : Tuple<int, int>
{
    public Pair(int item1, int item2) : base(item1, item2) { }

    public override bool Equals(object pair)
    {
        Pair dest = pair as Pair;
        return dest.Item1 == Item1 || dest.Item2 == Item1;
    }

    public override int GetHashCode()
    {
        return Item1 + Item2;
    }
}

Answer 2

This is what I would try

    public Dictionary<int, int> Pairs(int[] arr, int N)
    {
        // int N asssumes no arr > int32 max / 2 
        int len = arr.Length < N ? arr.Length / 2 : N / 2;
        Dictionary<int, int> d = new Dictionary<int, int>(len); 
                          // add is O(1) if count <= capacity 
        if(arr.Length == 0) return d;
        Array.Sort(arr);  // so it is O(n log n) I still take my chances with it
                          // that is n * log(n)         
        int start = 0;
        int end = arr.Length - 1;
        do
        {
            int ttl = arr[start] + arr[end];
            if (ttl == N)
            {
                if(!d.ContainsKey(arr[start]))
                      d.Add(arr[start], arr[end]); 
                      // if start <= end then pair uniquely defined by either 
                      // and a perfect hash (zero collisions)
                start++;
                end--;
            }
            else if (ttl > N)
                end--;
            else
                start++;
            if(start >= end)
                return d;
        }   while (true);
    }

Even with a HashSet based solution still use Dictionary(N/2) with Key <= Value

Or use Dictionary(arr.Length / 2)

Answer 3

First of all HashSet removes duplicate items. So iterating through HashSet or Array may yield different results since the array may have duplicate items.

Iterating through HashSet is ok. but note that it should not be used for only iterating purpose. BTW using HashSet is best option here because of O(1) for finding items.

Tuples are compared by reference inside HashSet. That means two different tuples with same items are never equal by default. since they always have different reference. (Sorry my mistake.) it seems tuples are compared by their items. But it compares only x.item1 to y.item1 and x.item2 to y.item2. so 1,2 and 2,1 are not equal. you can make them equal by setting another IEqualityComparer to hashset.

You should not be worry about memory leaks. when HashSet fails to add tuple the garbage collector will remove that tuple when the reference of that tuple is gone. Not immediately but when its needed.

static HashSet<Tuple<int, int>> PairsThatSumToN(int[] arr, int N)
{
    HashSet<int> hash = new HashSet<int>(arr);
    HashSet<Tuple<int, int>> result = new HashSet<Tuple<int, int>>(new IntTupleComparer());

    foreach(int i in arr)
    {
        int j = N - i;
        if (hash.Contains(j)) result.Add(new Tuple<int, int>(i, j));
    }
    return result;
}

public class IntTupleComparer : IEqualityComparer<Tuple<int, int>>
{
    public bool Equals(Tuple<int, int> x, Tuple<int, int> y)
    {
        return (x.Item1 == y.Item1 && x.Item2 == y.Item2) || (x.Item1 == y.Item2 && x.Item2 == y.Item1);
    }

    public int GetHashCode(Tuple<int, int> obj)
    {
        return (obj.Item1 + obj.Item2).GetHashCode();
    }
}

Answer 4

If the input set contains unique numbers, or the function must return only unique pairs, I think your second algorithm is the best. Just the result doesn't need to be a HashSet<Tuple<int, int>>, because the uniqueness is guaranteed by the algorithm - a simple List<Tuple<int, int>> would do the same, and better abstraction would be IEnumerable<Tuple<int, int>>. Here is how it looks implemented with C# iterator function:

static IEnumerable<Tuple<int, int>> UniquePairsThatSumToN(int[] source, int N)
{
    var set = new HashSet<int>();
    for (int i = 0; i < source.Length; i++)
    {
        var a = source[i];
        var b = N - a;
        if (set.Add(a) && set.Contains(b))
            yield return Tuple.Create(b, a);
    }
}

The key point is the line if (set.Add(a) && set.Contains(b)). Since both HashSet<T>.Add and HashSet<T>.Contains are O(1), the whole algorithm is therefore O(N).

With a relatively small modification we can make a function that returns all pairs (not only unique) like this

static IEnumerable<Tuple<int, int>> AllPairsThatSumToN(int[] source, int N)
{
    var countMap = new Dictionary<int, int>(source.Length);
    for (int i = 0; i < source.Length; i++)
    {
        var a = source[i];
        var b = N - a;
        int countA;
        countMap.TryGetValue(a, out countA);
        countMap[a] = ++countA;
        int countB;
        if (countMap.TryGetValue(b, out countB))
            while (--countB >= 0)
                yield return Tuple.Create(b, a);
    }
}