Find key with max value from SortedDictionary?

Question

I have a SortedDictionary how do I find the key associated with the max value? Do I have to loop through every KeyValuePair?

Answer 1

If dict is your SortedDictionary<,> (or any IDictionary<,>) and you want all the keys that correspond to the max value, first check that dict is not null or empty (you need at least one element). Then maybe this works:

var max = dict.Values.Max();
var relevantKeys = dict.Where(pair => max.Equals(pair.Value))
    .Select(pair => pair.Key);

Maybe it can be done more efficiently?

Answer 2

Use Enumerable.OrderByDescending() and then access the Key property of what First() returns like so:

 var dict = new SortedDictionary<string, string>
                       {
                           {"key1", "value3"},
                           {"key2", "value1"},
                           {"key3", "value2"},
                       };

        var max = dict.OrderByDescending(d => d.Value).First();
        var key = max.Key;

Answer 3

You can use the MaxBy method in MoreLinq to efficiently run this query.

var result =  dictionary.MaxBy(pair => pair.Value).Key;

This will only need to iterate the data once, as opposed to sorting the values and taking the first result (which will be O(n * log(n))).

Since only the keys, rather then the values, are sorted, there is no way of performing this query without at least looping through every keypair once.

Another option would be to have two SortedDictionaries. One would be the one that you already have, and the other would be a reverse dictionary. For each value in your current dictionary you could add it as a key to the second dictionary, and the value of the second dictionary would be the key in the first (if it's a one to many relationship rather than a one to one the value of the reverse lookup will need to be a list of items). While it will be programmatically "expensive" (more in memory than in time, but still some of both) to create this second dictionary, once you do you would be able to efficiently query based on values rather than keys.

Answer 4

Getting the key associated with the max value, means you are not actually using the default ordering of the SortedDictionary. This is because the SortedDictionar orders by Key, rather than Value. So to do what you want, you'd do it the old fashioned LINQ way:

sortedDict.OrderByDescending(kvp => kvp.Value).First().Key

Answer 5

To get all keys that hold a maximum of the value you are interested in, some dataprocessing has to be done. Actually this is quite comfortable in C#.

It can be accomplished by doing some combination of Linq

// first of all, group your dictionary by the value you want to have
var groups = dict.GroupBy(d => d.Value);

// then, order those groups by the value
var orderedGroups = groups.OrderBy(g => g.Key);

// after that, you have all the KeyValuePairs that hold the MaxValue here:
var maxKeys = orderedGroups.Last().ToList();

Have fun with it!