FlatMap for nested collections in Kotlin - Time & Space Complexity

Time Complexity: FlatMap for nested collections

O(n)

Understanding Time Complexity

When using flatMap on nested collections, it is important to understand how the time to run grows as the collections get bigger.

We want to know how many steps the program takes when it combines all inner lists into one big list.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val nestedList = listOf(
    listOf(1, 2, 3),
    listOf(4, 5),
    listOf(6, 7, 8, 9)
)

val flatList = nestedList.flatMap { innerList ->
    innerList.map { it * 2 }
}
    

This code takes a list of lists of numbers, doubles each number, and then combines all results into one list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing each inner list and mapping its elements.
• How many times: Once for each element inside every inner list.

How Execution Grows With Input

As the total number of elements inside all inner lists grows, the work grows roughly the same amount.

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

Pattern observation: The time grows directly with the total number of elements across all inner lists.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the total number of elements inside all nested lists combined.

Common Mistake

[X] Wrong: "Because there are two loops (flatMap and map), the time is squared, like O(n²)."

[OK] Correct: The inner map runs once per element, not nested inside another full loop. So the total steps add up linearly, not multiply.

Interview Connect

Understanding how flatMap works helps you explain how data is processed step-by-step in real projects, showing you can reason about code efficiency clearly.

Self-Check

What if we replaced map inside flatMap with a filter that sometimes skips elements? How would the time complexity change?

Practice

1. What does the flatMap function do when applied to a nested list in Kotlin?

easy

A. It filters elements based on a condition.

B. It sorts the nested lists in ascending order.

C. It transforms each element and flattens the result into a single list.

D. It converts the list into a set to remove duplicates.

Solution

1. Step 1: Understand flatMap behavior

   flatMap applies a transformation to each element and then flattens the nested results into one list.

2. Step 2: Compare with other functions

   Unlike sorting, filtering, or converting to a set, flatMap combines mapping and flattening in one step.

3. Final Answer:

   It transforms each element and flattens the result into a single list. -> Option C

4. Quick Check:

   flatMap = transform + flatten [OK]

Hint: Remember: flatMap = map + flatten in one step [OK]

Common Mistakes:

• Confusing flatMap with filter or sort
• Thinking flatMap removes duplicates
• Assuming flatMap only maps without flattening

2. Which of the following is the correct syntax to use flatMap on a list of lists named nestedList in Kotlin?

easy

A. nestedList.flatMap { it }

B. nestedList.flatMap()

C. nestedList.flatMap -> it

D. nestedList.flatMap { it.flatten() }

Solution

1. Step 1: Identify correct lambda syntax

   The flatMap function requires a lambda to transform each element. { it } returns each inner list as is.

2. Step 2: Check other options

   nestedList.flatMap() misses lambda, C uses wrong arrow syntax, D uses flatten() incorrectly on flat inner lists.

3. Final Answer:

   nestedList.flatMap { it } -> Option A

4. Quick Check:

   flatMap needs a lambda like { it } [OK]

Hint: flatMap always needs a lambda block { } [OK]

Common Mistakes:

• Omitting the lambda block
• Using arrow (->) instead of curly braces
• Using flatten() instead of identity mapping

3. What is the output of the following Kotlin code?

val nested = listOf(listOf(1, 2), listOf(3, 4))
val result = nested.flatMap { it.map { it * 2 } }
println(result)

medium

A. [[2, 4], [6, 8]]

B. [1, 2, 3, 4]

C. [2, 4, [6, 8]]

D. [2, 4, 6, 8]

Solution

1. Step 1: Understand inner map transformation

   Each inner list element is multiplied by 2, so listOf(1,2) becomes listOf(2,4), and listOf(3,4) becomes listOf(6,8).

2. Step 2: Apply flatMap flattening

   flatMap flattens the transformed lists into one list: [2, 4, 6, 8].

3. Final Answer:

   [2, 4, 6, 8] -> Option D

4. Quick Check:

   flatMap + map doubles and flattens [OK]

Hint: flatMap flattens after map transformation [OK]

Common Mistakes:

• Expecting nested lists instead of flat list
• Ignoring the inner map multiplication
• Confusing output with original nested list

4. Identify the error in this Kotlin code snippet using flatMap:

val nested = listOf(listOf(1, 2), listOf(3, 4))
val result = nested.flatMap { it * 2 }
println(result)

medium

A. flatMap requires a filter inside the lambda.

B. Cannot multiply a list by an integer directly.

C. The variable 'nested' is not defined.

D. flatMap should be replaced with map.

Solution

1. Step 1: Analyze the lambda expression

   The lambda tries to multiply it (a list) by 2, which is invalid in Kotlin.

2. Step 2: Understand flatMap requirements

   flatMap expects a lambda returning an iterable, but it * 2 causes a type error.

3. Final Answer:

   Cannot multiply a list by an integer directly. -> Option B

4. Quick Check:

   List * Int is invalid in Kotlin [OK]

Hint: Check types inside lambda; lists can't be multiplied by numbers [OK]

Common Mistakes:

• Assuming list * number works like in some other languages
• Thinking flatMap needs a filter
• Confusing map and flatMap usage

5. Given a list of students where each student has a list of grades, how can you use flatMap to get a single list of all grades above 70?

data class Student(val name: String, val grades: List<Int>)
val students = listOf(
    Student("Alice", listOf(80, 65)),
    Student("Bob", listOf(90, 72)),
    Student("Carol", listOf(60, 85))
)
// Fill in the blank:
val passingGrades = students.flatMap { ________ }
println(passingGrades)

hard

A. it.grades.filter { grade -> grade > 70 }

B. it.grades.map { grade -> grade > 70 }

C. it.grades.filter { grade -> grade < 70 }

D. it.grades

Solution

1. Step 1: Filter grades above 70 for each student

   Inside the lambda, use it.grades.filter { grade -> grade > 70 } to keep only passing grades.

2. Step 2: Use flatMap to flatten all filtered grades

   flatMap combines all filtered lists into one flat list of passing grades.

3. Final Answer:

   it.grades.filter { grade -> grade > 70 } -> Option A

4. Quick Check:

   flatMap + filter extracts and flattens passing grades [OK]

Hint: Use flatMap with filter inside to flatten filtered results [OK]

Common Mistakes:

• Using map instead of filter, resulting in booleans
• Filtering for grades below 70 by mistake
• Not filtering and returning all grades