Longest list in SortedList of Lists

Question

I have a SortedList of Lists and I am interested in finding the KEY that corresponds to the longest list (list with the most items in it). In code, that looks like:

// how the list is defined:
var myList = new SortedList<long, List<string>>();

// EXAMPLE data only:
myList.Add(0, new List<string>());
myList[0].AddRange(new []{"a", "b", "c"});

myList.Add(8, new List<string>());
myList[8].AddRange(new []{"1", "2"});

myList.Add(23, new List<string>());
myList[23].AddRange(new []{"c", "d", "e", "f", "g"});

In the above example the result should be "23" since that is the key that goes with the longest list.

I know how to write this with a for loop, but I think this should be a simple to do with LINQ. That said, I can't seem to get the syntax quite right! Any help is appreciated!

Answer 1

There's maybe a more efficient way, but you can order by count (of value) descending, and take first.

myList.OrderByDescending(m => m.Value.Count()).First().Key;

of course, if you want all the keys with highest count (they may be multiple values with same length), you should do a group by count.

Something like that.

myList.GroupBy(m => m.Value.Count())
      .OrderByDescending(m => m.Key)//I'm the key of the group by
      .First()
      .Select(g => g.Key);//I'm the key of the SortedList

So if you add to your sample an item with same list length

myList.Add(24, new List<string>());
myList[24].AddRange(new[] {"a", "b", "c", "d", "e"});

you will get 23 And 24.

same could be achieved with

from item in myList
let maxCount = myList.Max(x => x.Value.Count())
where item.Value.Count() == maxCount
select item.Key;

Answer 2

Whilst a sort will give you correct results, it requires O(n log n) time to execute, whilst is asymptotically higher than a simple O(n) sweep:

int maxLength = myList.Max(x => x.Value.Count);
var longestKeys = myList.Where(x => x.Value.Count == maxLength).Select(x => x.Key);

Answer 3

using MaxBy of morelinq

var key = myList.MaxBy(x => x.Value.Count()).Key;

Answer 4

Just for the sake of adding yet another way of doing it, you can achieve this with Linq's Aggregate method like so:

//Extension method
public static long MaxIndex(this SortedList<long, List<string>> list)
{
    return list.Aggregate(
        new { MaxValue = -1, Key = -1L },
            ((agg, current) => (current.Value.Count.CompareTo(agg.MaxValue) > 0 || agg.Key == -1) ?
        new { MaxValue = current.Value.Count, Key = current.Key } :
        new { MaxValue = agg.MaxValue, Key = agg.Key })).
        Key;
}

// how the list is defined:
var myList = new SortedList<long, List<string>>();

// EXAMPLE data only:
myList.Add(0, new List<string>());
myList[0].AddRange(new[] { "a", "b", "c" });

myList.Add(8, new List<string>());
myList[8].AddRange(new[] { "1", "2" });

myList.Add(23, new List<string>());
myList[23].AddRange(new[] { "c", "d", "e", "f", "g" });

var idx = myList.MaxIndex();

This is adapted from this SO answer: https://stackoverflow.com/a/15068695/172769

Cheers