Flatten an Array in C# [duplicate]

Question

In C# what is the shortest code to flatten an array?

For example, I want

[[1,2],[2,3],[4,5]]

into the array

[1,2,3,4,5]

I am looking for the shortest way to do so.

Answer 1

Maybe I'm reading "shortest code" the wrong way, but I would propose using LINQ SelectMany and Distinct:

var values = new[]
{
    new[] { 1, 2 },
    new[] { 2, 3 },
    new[] { 4, 5 },
};

var flattenedUniqueValues = values.SelectMany(x => x).Distinct();

Answer 2

Converting a staggered array to a 1-dimensional array is simple and can be done in O(n) time and n space (where n is the sum of 2nd-dimension array lengths), however in your example you seem to remove duplicate values - that is not flattening an array, but it can still be done in O(n) time but will require O(2n) space because you need a hashtable for O(1) duplicate value lookups.

A possible problem exists in knowing in advance how many elements will exist in the final array. A straightforward solution is to append to a List<T> and calling .ToArray() at the end, but that will result in O(2n) time and O(3n) space (but potentially more owing to List<T> internal reallocations):

Int32[][] jagged = ...
HashSet<Int32> seen = new HashSet<Int32>();
List<Int32> ret = new List<Int32>();

for(int i = 0; i < jagged.Length; i++) {
    for(int j = 0; j < jagged[i].Length; j++) {
        Int32 val = jagged[i][j];
        if( !seen.Contains( val ) ) {
            ret.Add( val );
            seen.Add( val );
        }
    }
}

return ret.ToArray(); // This takes O(n) time and will allocate O(n) additional space.

Another solution exists by doing 2 passes yourself: the first to determine the size of the output, then the second pass to generate it - which will result in less copying: exactly O(2n) time and exactly O(2n) space:

Int32[][] jagged = ...
HashSet<Int32> seen = new HashSet<Int32>();

// Pass 1
for(int i = 0; i < jagged.Length; i++) {
    for(int j = 0; j < jagged[i].Length; j++) {
        Int32 val = jagged[i][j];
        seen.Add( val ); // HashSet.Add is safe/idempotent
    }
}

Int32[] ret = new Int32[ seen.Count ];

// Pass 2
seen.Clear();

Int32 retIdx = 0;
for(int i = 0; i < jagged.Length; i++) {
    for(int j = 0; j < jagged[i].Length; j++) {
        Int32 val = jagged[i][j];
        if( !seen.Contains( val ) ) {
            ret[++retIdx] = val;
            seen.Add( val );
        }
    }
}

return ret;