FindTwoSums using Tuple

Question

I am writing a function that, given a list and a target sum, returns zero-based indices of any two distinct elements whose sum is equal to the target sum. If there are no such elements, the function should return null.

For example,

 FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12) 

should return any of the following tuples of indices:

1, 4 (3 + 9 = 12)
2, 3 (5 + 7 = 12)
3, 2 (7 + 5 = 12)
4, 1 (9 + 3 = 12)

Note: I made my code return the first sum equal to 12.

So far, I came up with the following:

using System;
using System.Collections.Generic;

class TwoSum
{
    public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
    {
       int first_i =0, global_sum=0, second_i=1;

        if(list.Count == 0 || sum == 0 ){
            return null;
        }


        for(int i = first_i ; i< list.Count; i++)
        {
            for(int j=second_i; j<list.Count; j++)
            {
                        if(i != list.Count)
                            {
                                global_sum += list[i] + list[j];

                                if(global_sum == sum)
                                    {
                                         var tuple1 = Tuple.Create(i,j);
                                      return tuple1;
                                    }
                                global_sum = 0;
                            }
                        else
                            {
                                break;
                            }

            }
        }
        return null;

    }

    public static void Main(string[] args)
    {
        Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12);
        Console.WriteLine(indices.Item1 + " " + indices.Item2);
    }
}

Everything was working fine and I scored 75%. But in terms of performance, my code did badly as I got a review saying:

performance test- The code too long to calculate an answer. Analyse how your code behaves when the input increases in size and see if you can make it work faster

Answer 1

Formatting

The indenting and placement of braces is inconsistent in the program, and it hurts readability. Instead of this:

    for(int i = first_i ; i< list.Count; i++)
    {
        for(int j=second_i; j<list.Count; j++)
        {
                    if(i != list.Count)
                        {
                            global_sum += list[i] + list[j];

                            if(global_sum == sum)
                                {
                                     var tuple1 = Tuple.Create(i,j);
                                  return tuple1;
                                }
                            global_sum = 0;
                        }
                    else
                        {
                            break;
                        }

        }
    }

This would be have been much better:

    for (int i = first_i; i < list.Count; i++)
    {
        for (int j = second_i; j < list.Count; j++)
        {
            if (i != list.Count)
            {
                global_sum += list[i] + list[j];

                if (global_sum == sum)
                {
                    var tuple1 = Tuple.Create(i, j);
                    return tuple1;
                }

                global_sum = 0;
            }
            else
            {
                break;
            }
        }
    }

Strange condition in loop body

The conditional in the body of the nested loop is pointless, as it can never be true. You can simply remove it:

for (int i = first_i; i < list.Count; i++)
{
    for (int j = second_i; j < list.Count; j++)
    {
        global_sum += list[i] + list[j];

        if (global_sum == sum)
        {
            var tuple1 = Tuple.Create(i, j);
            return tuple1;
        }

        global_sum = 0;
    }
}

Unnecessary variables

The name global_sum is not great. There's nothing "global" about that sum. It's just sum. And you don't need it a variable for it anyway. You could change this code:

        global_sum += list[i] + list[j];

        if (global_sum == sum)
        {
            var tuple1 = Tuple.Create(i, j);
            return tuple1;
        }

        global_sum = 0;

Like this:

        var global_sum = list[i] + list[j];

        if (global_sum == sum)
        {
            var tuple1 = Tuple.Create(i, j);
            return tuple1;
        }

At this point, notice that you don't really need this variable at all, you could write the expression directly in the if statement. The tuple1 variable is also pointless. The code can be reduced to:

        if (list[i] + list[j] == sum)
        {
            return Tuple.Create(i, j);
        }

---

first_i and second_i are also rather useless, and would have been to use their values directly inside the loop statements.

Also keep in mind that declaring variables at the top of their scope, when they are not used until much later, is not a recommended practice. It's best to declare a variable right before you need it.

Correctness

As @RiskyMartin hinted, given an input list 1, 6, 9, the output will be incorrectly (6, 6). In other words, you need to make sure that i and j indexes are not equal.

Performance

Of course, none of the above help with the performance. The algorithm is \$O(n^2)\$: you try all permutation of pairs.

To make this faster, you can sort the input list, and then form pairs using two pointers, one going from the start and one going from the end. Move the pointers closer when the sum of the pointed values is above the target sum. The performance of this algorithm will be \$O(n\log(n))\$: the sorting step is \$O(n\log(n))\$, the search step with two pointers is \$O(n)\$.

For example, given 1, 2, 5, 7, 9, the first pointer starts at 1, the second at 9. 1 + 9 is less than 12, so you advance the first pointer. 2 + 9 is less than 12, so you advance the first pointer. 5 + 9 is greater than 12, so you move the second pointer. 5 + 7 is a match, you return it.

Just like in the original program, make sure the two pointers don't point to the same element, because that could produce an invalid match, potentially using the same element twice to make the sum.

Answer 2

You could potentially make your code a bit cleaner, even easier to read:

protected static Dictionary<int, int> GetVariableFromSum(int sum, params int[] variables)
{
     var collection = new Dictionary<int, int>();
     if(!variables.Any())
          return collection;

     foreach(var variable in variables)
          for(int counter = 1; counter < variables.Count(); counter++)
          {
               var total = (variable + variables[counter]);
               if(total == sum)
                    collection.Add(variable, variables[counter]);
          }

     return collection;
}

The Dictionary simply because I like it better than a Tuple. But otherwise the code is a bit more expressive, not better than the recommendations above, but a bit more concise I believe.