How to convert an array to a look up data structure

Question

I've an array of integers as shown below:

2 2 4 3

I want to create a Lookup for above data. I want that for each unique number present in the array, I can maintain the indexes as a linked list in case it gets repeated:

2 - 0,1
4 - 2
3 - 3

I tried something via LINQ which seems like a standard way of getting an instance of Lookup class but this is not compiling:

var prices = new int[] { 2,2,4,3};
var lookUp = prices.ToLookup<int,int>((x, i) => i + 1);

I don't understand why can I not simply instantiate the Lookup class and add items into it like we do in Dictionary class. Whenever it finds the same key being added into it again, it should simply create a collection instead. Sample code that I was speculating to work:

var prices = new int[] { 2,2,4,3};
var lookUp = new Lookup<int,int>();        
for (int i = 0; i < prices.Length; i++)
    lookUp.Add(prices[i], i);

This again doesn't compile as a note on MSDN says:

There is no public constructor to create a new instance of a Lookup. Additionally, Lookup objects are immutable, that is, you cannot add or remove elements or keys from a Lookup object after it has been created.

Can someone help me achieving my key objective? I'm struggling a bit to wrap my head around how Lookup implementation has been made available in C#.

Nkosi · Accepted Answer · 2018-03-31T16:10:23.890

The gist of creating the lookup is to first map the vales in the array to their index/position in the array and then create the lookup from the mapping using the vlaue as the key and the index of that value for the lookup item.

The following example demonstrates converting the array into the desired lookup

using System;
using System.Linq;

public class Program {
    public static void Main() {
        var prices = new int[] { 2, 2, 4, 3 };

        var map = prices.Select((value, index) => new { index, value });

        var lookUps = map.ToLookup(_ => _.value, _ => _.index);

        foreach(var item in lookUps) {
            var value = item.Key;
            var indexes = string.Join(",", item);
            var output = String.Format("{0} - {1}", value, indexes);
            Console.WriteLine(output);
        }
    }
}

Which output

2 - 0,1
4 - 2
3 - 3

for the provided input.

Just one quick query about complexity. I'm sure it is of order `O(n)` but does the `Select` projection and the call to `ToLookup` will cause the loop to run twice internally? i.e. `O(2n)`. `O(2n)` is still of order `O(n)` only but I just want to know if there will be in all two iterations or only one to create the look up. You don't have to consider the `foreach` loop that you put explicitly to show the output. — RBT, Apr 01 '18 at 16:56

How to convert an array to a look up data structure

1 Answers1