SelectMany for flattening in C Sharp (C#) - Time & Space Complexity

Time Complexity: SelectMany for flattening

O(n)

Understanding Time Complexity

When we use SelectMany to flatten collections, we want to know how the time to run grows as the input grows.

We ask: How does the number of operations change when the input lists get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var listOfLists = new List<List<int>> {
    new List<int> {1, 2, 3},
    new List<int> {4, 5},
    new List<int> {6}
};

var flattened = listOfLists.SelectMany(innerList => innerList).ToList();
    

This code takes a list of lists of numbers and combines all inner lists into one single list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Going through each inner list and then each item inside it.
• How many times: Once for every item inside every inner list combined.

How Execution Grows With Input

Imagine the total number of items inside all inner lists combined is n.

Input Size (n)	Approx. Operations
10	About 10 operations
100	About 100 operations
1000	About 1000 operations

Pattern observation: The work grows directly with the total number of items to flatten.

Final Time Complexity

Time Complexity: O(n)

This means the time to flatten grows in a straight line with the total number of items inside all lists.

Common Mistake

[X] Wrong: "SelectMany runs in constant time no matter how big the lists are."

[OK] Correct: Actually, SelectMany must look at every item to combine them, so time grows with total items.

Interview Connect

Understanding how flattening collections scales helps you explain efficiency clearly and shows you know how data size affects performance.

Self-Check

"What if the inner lists were all empty except one very large list? How would the time complexity change?"

Practice

1. What does the SelectMany method do in C# when used on a list of lists?

easy

A. It sorts each inner list individually.

B. It filters the outer list based on a condition.

C. It flattens the nested lists into a single list containing all elements.

D. It creates a dictionary from the nested lists.

Solution

1. Step 1: Understand the structure of nested lists

   A list of lists means you have many small lists inside one big list.

2. Step 2: Role of SelectMany

   SelectMany takes each small list and combines all their elements into one big flat list.

3. Final Answer:

   It flattens the nested lists into a single list containing all elements. -> Option C

4. Quick Check:

   SelectMany flattens nested lists = B [OK]

Hint: SelectMany flattens nested lists into one list fast [OK]

Common Mistakes:

• Thinking SelectMany sorts or filters instead of flattening
• Confusing SelectMany with Select which keeps nested structure
• Assuming SelectMany creates dictionaries

2. Which of the following is the correct syntax to flatten a list of lists List numbers using SelectMany?

easy

A. var flat = numbers.SelectMany(x => x);

B. var flat = numbers.Select(x => x);

C. var flat = numbers.SelectMany(x => x.ToString());

D. var flat = numbers.SelectMany(x => x.Count());

Solution

1. Step 1: Understand SelectMany syntax

   SelectMany expects a function that returns an inner collection to flatten.

2. Step 2: Check each option

   var flat = numbers.SelectMany(x => x); returns each inner list as is, which is correct. var flat = numbers.Select(x => x); uses Select, not flattening. Options C and D return wrong types (string and int), not collections.

3. Final Answer:

   var flat = numbers.SelectMany(x => x); -> Option A

4. Quick Check:

   SelectMany with identity function flattens = A [OK]

Hint: Use SelectMany with identity function to flatten lists [OK]

Common Mistakes:

• Using Select instead of SelectMany
• Returning non-collections inside SelectMany
• Trying to flatten by counting elements

3. What is the output of the following code?

var data = new List {
  new List<int> {1, 2},
  new List<int> {3, 4},
  new List<int> {5}
};
var result = data.SelectMany(x => x).ToList();
Console.WriteLine(string.Join(",", result));

medium

A. 12345

B. 1,2;3,4;5

C. System.Collections.Generic.List`1[System.Int32]

D. 1,2,3,4,5

Solution

1. Step 1: Understand SelectMany flattening

   SelectMany flattens all inner lists into one list: [1,2,3,4,5].

2. Step 2: Output formatting

   string.Join with "," joins elements with commas, so output is "1,2,3,4,5".

3. Final Answer:

   1,2,3,4,5 -> Option D

4. Quick Check:

   Flattened list joined by commas = D [OK]

Hint: SelectMany flattens, string.Join prints with commas [OK]

Common Mistakes:

• Expecting nested list output instead of flat
• Confusing ToString output of list object
• Missing commas in output

4. Identify the error in this code snippet that tries to flatten a list of lists:

List words = new() {
  new List<string> {"apple", "banana"},
  new List<string> {"cat", "dog"}
};
var flatWords = words.SelectMany(w => w.Length).ToList();

medium

A. The list initialization syntax is incorrect.

B. Using w.Length returns int, not a collection, causing a compile error.

C. Missing parentheses after SelectMany call.

D. ToList() cannot be called after SelectMany.

Solution

1. Step 1: Analyze the lambda inside SelectMany

   The lambda uses w => w.Length, which returns an int, not a collection.

2. Step 2: Understand SelectMany requirements

   SelectMany expects a function returning a collection to flatten, not a single int value.

3. Final Answer:

   Using w.Length returns int, not a collection, causing a compile error. -> Option B

4. Quick Check:

   SelectMany needs collections, not int = C [OK]

Hint: SelectMany lambda must return collections, not single values [OK]

Common Mistakes:

• Returning single values instead of collections in SelectMany
• Confusing Length property with collection
• Assuming ToList() causes error

5. Given a list of students where each student has a list of grades, how would you use SelectMany to get a list of all grades above 80 from all students?

class Student {
  public string Name { get; set; }
  public List<int> Grades { get; set; }
}

List<Student> students = new() {
  new Student { Name = "Anna", Grades = new List<int> { 90, 70 } },
  new Student { Name = "Ben", Grades = new List<int> { 85, 60 } }
};

// Fill in the blank to get all grades > 80
var highGrades = students.SelectMany(__________).ToList();

hard

A. s => s.Grades.Where(g => g > 80)

B. s => s.Grades

C. s => s.Name

D. s => s.Grades.Count

Solution

1. Step 1: Understand the goal

   We want all grades above 80 from all students combined.

2. Step 2: Use SelectMany with filtering inside

   s => s.Grades.Where(g => g > 80) filters grades > 80 inside SelectMany, flattening only those grades.

3. Step 3: Why not others?

   s => s.Grades flattens all grades, including low ones like 70 and 60. Options C and D return wrong types (string and int).

4. Final Answer:

   s => s.Grades.Where(g => g > 80) -> Option A

5. Quick Check:

   SelectMany with filtered inner lists = A [OK]

Hint: Filter inside SelectMany to flatten only needed items [OK]

Common Mistakes:

• Flattening all grades without filtering
• Returning non-collections in SelectMany
• Using wrong property like Name or Count