Reverse Dictionary: Group from child array elements and get its minimum key

Question

Objective

I have following array and would like to group by each child and get its smallest Id:-

var list = new[]
{
    new { Id = 1, Childs = new [] { 'a', 'b' } },
    new { Id = 2, Childs = new [] { 'a' } },
    new { Id = 3, Childs = new [] { 'a', 'c' } },
    new { Id = 4, Childs = new [] { 'b' } },
    new { Id = 5, Childs = new [] { 'b' } },
    new { Id = 6, Childs = new [] { 'b', 'c' } },
};

Attempt

var groups = list
                .SelectMany(item => item.Childs)
                .Distinct() // for each unique child
                .ToDictionary(
                    child => child, // with each child as key
                    child => list.Where(item =>
                                item.Childs.Any(c =>
                                    c == child)) // get items with corresponding child
                                .Min(item => item.Id)); // extract min Id

foreach (var g in groups)
{
    Console.WriteLine($"{ g.Key }: { g.Value }");
}

// Prints
// a: 1
// b: 1
// c: 3

Rationale

a contains in Id 1, 2 and 3 and the smallest is 1.

Improvement

I'm trying to solve it with LINQ and thinking GroupBy would be the go-to solution but I'm stuck with splitting each child element as the key.

I would really appreciate if someone have any idea to solve it in a more elegant way! 🙇

Answer 1

First, you're going through the list of items to find all distinct children. Then, for each child, you're going through the list again to find all items that it belongs to, and then you take the lowest item ID. That's \$O(n^2)\$ in worst-case scenarios, though in practice it'll be closer to \$O(n)\$ if you don't have too many distinct children.

A more efficient approach would be to create ID-child pairs, which allows you to group item IDs per child, and then extract the lowest ID from each group:

list.SelectMany(item => item.Childs.Select(child => new { Id = item.Id, Child = child }))
    .GroupBy(item => item.Child, item => item.Id)
    .ToDictionary(
        group => group.Key,
        group => group.Min(id => id));

However, creating a dictionary with a nested loop is still several times faster, and less GC-intensive, while taking about the same 'amount' of code, so I'm not so sure about Linq being the best choice here.

Answer 2

Indeed, you could use GroupBy but I think it's easier to solve with the query syntax because we also need the item from the first list to sort by its Id. Without it, we would need to do additional lookups like you do.

var result =     
    from item in items // from + from = SelectMany
    from child in item.Children
    orderby item.Id // sort in ascending order
    group item.Id by child into g // group by child
    select (Child: g.Key, MinId: g.First()); // the first item in each group is the min-id

If you use select g instead, you'll get IGrouping<char, int> which you can easily turn into a dictionary or a lookup.