FlatMap for nested collections in Swift - 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 work grows as the size of the collections increases.

We want to know how many steps the program takes as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

let nestedArrays = [[1, 2], [3, 4, 5], [6]]
let flattened = nestedArrays.flatMap { innerArray in
    innerArray.map { $0 * 2 }
}
print(flattened)
    

This code doubles each number inside nested arrays and then flattens them into a single array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the total number of elements inside all inner arrays grows, the work grows proportionally.

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

Pattern observation: The number of steps grows directly with the total number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the operation grows in a straight line with the total number of elements inside all nested arrays.

Common Mistake

[X] Wrong: "Because there are nested arrays, the time complexity must be quadratic or worse."

[OK] Correct: The operation visits each element only once, so the total work depends on the total number of elements, not the number of arrays squared.

Interview Connect

Understanding how nested collections affect time helps you explain your code clearly and shows you can think about efficiency in real situations.

Self-Check

"What if the inner arrays were very large but the number of inner arrays was small? How would the time complexity change?"