CODEWITHSUNDEEP
c#listperformancelatencylow-latency
nissedanielsen
nissedanielsen

Reputation: 41

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

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;

Upvotes: 3

Views: 893

Answers (4)

Guru Stron
Guru Stron

Reputation: 141895

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).

Upvotes: 6

Apollo13
Apollo13

Reputation: 11

You can try this simple way:

list.Sort();
list.Reverse();
var secondHighest=list.Take(2).Sum();
 
return secondHighest;

or

 list=list.OrderByDescending(o=>o).ToList();
 var secondHighest=list.Take(2).Sum();
 
return secondHighest;

At first, it sorts your list, then reverses it , now you have descending sorted list , than it will take 2 highest elements and aggregate them .

Upvotes: -1

Muhammad Raza
Muhammad Raza

Reputation: 35

LINQ can be a very good solution for it.

long sum = 0;
if(list.Count > 1) 
  sum = list.OrderByDescending(z=>z).Take(2).Sum();
else
  sum = list.Sum();

Upvotes: 1

ProgrammingLlama
ProgrammingLlama

Reputation: 38757

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.

Upvotes: 3

Related Questions