C# jagged array to list of lists

Question

given a jagged array:

int[][] edges = new int[][] 
            {
                new int[] {0,1},
                new int[] {0,2},
                new int[] {0,3},
                new int[] {1,4},
            };

is there a more elegant way to do this:

var adjlist = new List<List<int>>();
            for(int i=0; i<n; i++)
            {
                adjlist.Add(new List<int>());
            }
            
            foreach(var arr in edges)
            {
                int src = arr[0];
                int dst = arr[1];

                adjlist[src].Add(dst);
                adjlist[dst].Add(src);
            }

something that improves on the time complexity for this would be ideal.

Thank you.

There is nothing can be done to improve time complexity as it is already as fast as it can get - linear time for the first dimension (new List<>(), list indexing and adding items to a list are constant time operations). — Alexei Levenkov
– Alexei Levenkov, Commented Jan 14, 2021 at 3:24
Is this code working as you expect / want? because its doing a fairly unusual and suspect operation — TheGeneral
– TheGeneral, Commented Jan 14, 2021 at 3:25
The code works. It was for a leetcode problem 261 and passes the tests there. To convert an edge list to an undirected graph. — user2227484
– user2227484, Commented Jan 14, 2021 at 12:10

halfer · Accepted Answer · 2021-01-17 10:16:52Z

7

My assumption is the code in your example is not working as you intended (I may be wrong). However converting a jagged array to a list of lists should be as simple as the following. I doubt you will get much more efficient than this, though you could benchmark.

The following is O(n), meaning something somewhere needs to iterate over each element. That's to say, the memory can't be magicked. On saying that, ToList will call the List constructor with the collection and use the instance member CopyTo which in-turn uses Array.Copy and as such is extremely optimized for the data type and platform.

var results = edges.Select(x => x.ToList()).ToList();

edited Jan 17, 2021 at 10:16

halfer

20.2k20 gold badges110 silver badges207 bronze badges

answered Jan 14, 2021 at 3:04

TheGeneral

82k9 gold badges110 silver badges151 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

C# jagged array to list of lists

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related