How to return sum of two highest value in List<int> in most efficient way? C#

Question

I'm trying to pass a pre-written test with focus on performance. What is the most efficient way to return the sum of the two highest numbers in a List of int? I have tried the following and according to the test it wasn't fast enough when it comes to larger lists:

1.  list.Sort();
    list.Reverse();
    return list[0] + list[1];

2.  return list.OrderByDescending(num => num).FirstOrDefault() + list.OrderByDescending(num => num).Skip(1).FirstOrDefault();

3.  var secondHighest = list.Distinct()
                            .OrderByDescending(i => i)
                            .Skip(1)
                            .First();

    return list.Max() + secondHighest;

Answer 1

Any straightforward sorting operation would be O(n*log(n)) (OrderBy(Descending), Sort) at best (on random data) though current task is achievable in O(n) with a simple loop (assuming there are at least 2 items in the list of course, for the case when there are 2 or less elements just return list.Sum()):

var first = int.MinValue;
var second = int.MinValue;
foreach(var i in list)
{
    if(i > first)
    {
        second = first;
        first = i;
    }
    else if(i > second)
    {
        second = i;
    }
}

var result = first + second;

Also it worth noting that there can be implementation depended LINQ optimizations for some of cases like combination of OrderBy(Descending)with operators like First(OrDefault) or possibly Take (see one, two, three).

Answer 2

Well, I'm proposing this algorithm:

highest = 0
highestSet = false
secondHighest = 0
secondHighestSet = false
foreach item in list
    if item >= highest or !highestSet
        if highestSet
          secondHighest = highest
        highestSet = true
        highest = item
    else if item >= secondHighest or !secondHighestSet
        secondHighestSet = true
        secondHighest = item

return highest + secondHighest

Input set of [3, 2, 3, 2], it will return 6. This is O(n) time complexity.

For a set of [3], it will return 3.