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?"

Practice

1. What does the flatMap function do when applied to a nested array in Swift?

easy

A. It flattens the nested arrays into a single array by combining all elements.

B. It sorts the nested arrays in ascending order.

C. It removes duplicate elements from the nested arrays.

D. It converts the nested arrays into a dictionary.

Solution

1. Step 1: Understand the purpose of flatMap

   The flatMap function is designed to take a collection of collections and combine them into one single collection by flattening the nested structure.

2. Step 2: Identify the effect on nested arrays

   When applied to nested arrays, flatMap merges all inner arrays into one continuous array containing all elements.

3. Final Answer:

   It flattens the nested arrays into a single array by combining all elements. -> Option A

4. Quick Check:

   flatMap flattens nested arrays = A [OK]

Hint: Remember: flatMap flattens nested arrays into one array [OK]

Common Mistakes:

• Thinking flatMap sorts the array
• Confusing flatMap with removing duplicates
• Assuming flatMap converts arrays to dictionaries

2. Which of the following is the correct syntax to flatten a nested array let nested = [[1, 2], [3, 4]] using flatMap in Swift?

easy

A. let flat = nested.flatten()

B. let flat = nested.map { $0 }

C. let flat = nested.flatMap()

D. let flat = nested.flatMap { $0 }

Solution

1. Step 1: Recall flatMap syntax

   The correct syntax for flattening nested arrays uses flatMap with a closure that returns each inner array: nested.flatMap { $0 }.

2. Step 2: Evaluate each option

   let flat = nested.flatMap { $0 } uses the correct closure syntax. let flat = nested.map { $0 } uses map which does not flatten. let flat = nested.flatMap() is invalid syntax. let flat = nested.flatten() uses a non-existent method flatten().

3. Final Answer:

   let flat = nested.flatMap { $0 } -> Option D

4. Quick Check:

   flatMap with closure { $0 } flattens nested arrays [OK]

Hint: Use flatMap with closure { $0 } to flatten nested arrays [OK]

Common Mistakes:

• Using map instead of flatMap
• Calling flatMap without closure
• Using non-existent flatten() method

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

let nested = [[1, 2], [3, 4], [5]]
let result = nested.flatMap { $0.map { $0 * 2 } }
print(result)

medium

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

B. [2, 4, 6, 8, 10]

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

D. [1, 4, 9, 16, 25]

Solution

1. Step 1: Understand the inner map operation

   Each inner array is mapped to a new array where each element is multiplied by 2, so [1,2] becomes [2,4], [3,4] becomes [6,8], and [5] becomes [10].

2. Step 2: Apply flatMap to flatten the mapped arrays

   The flatMap then flattens these arrays into a single array: [2, 4, 6, 8, 10].

3. Final Answer:

   [2, 4, 6, 8, 10] -> Option B

4. Quick Check:

   flatMap + map doubles and flattens = [2,4,6,8,10] [OK]

Hint: flatMap flattens after map transforms inner elements [OK]

Common Mistakes:

• Confusing flatMap with map output
• Expecting nested arrays instead of flattened
• Multiplying elements incorrectly

4. Identify the error in the following Swift code that attempts to flatten a nested array:

let nested = [["a", "b"], ["c"]]
let flat = nested.flatMap()
print(flat)

medium

A. flatMap requires a closure to specify how to flatten the nested arrays.

B. flatMap cannot be used on arrays of strings.

C. The variable 'flat' is immutable and cannot be assigned.

D. The print statement syntax is incorrect.

Solution

1. Step 1: Check flatMap usage

   The flatMap function requires a closure to specify how to flatten the nested arrays, such as { $0 }. Calling flatMap() without arguments is invalid.

2. Step 2: Verify other parts of the code

   Arrays of strings can be flattened with flatMap, variables can be assigned with let, and print syntax is correct.

3. Final Answer:

   flatMap requires a closure to specify how to flatten the nested arrays. -> Option A

4. Quick Check:

   flatMap needs closure { $0 } to flatten [OK]

Hint: Always provide closure { $0 } when using flatMap on nested arrays [OK]

Common Mistakes:

• Calling flatMap without closure
• Thinking flatMap can't flatten strings
• Misunderstanding let variable assignment
• Assuming print syntax is wrong

5. Given a nested array of optional integers let nested: [[Int?]] = [[1, nil], [3, 4], [nil]], which Swift code using flatMap correctly produces a flat array of non-nil integers?

hard

A. let flat = nested.flatMap { $0.filter { $0 != nil } }

B. let flat = nested.flatMap { $0.map { $0! } }

C. let flat = nested.flatMap { $0.compactMap { $0 } }

D. let flat = nested.flatMap { $0 }

Solution

1. Step 1: Understand the data and goal

   The nested array contains optional integers, some are nil. The goal is to flatten and remove nil values, keeping only non-nil integers.

2. Step 2: Analyze each option

   let flat = nested.flatMap { $0.compactMap { $0 } } uses compactMap inside flatMap to unwrap and remove nils, then flatten. let flat = nested.flatMap { $0.map { $0! } } force unwraps which can crash if nil exists. let flat = nested.flatMap { $0.filter { $0 != nil } } filters nil but keeps optionals, so result is nested optionals. let flat = nested.flatMap { $0 } just flattens but keeps nils.

3. Final Answer:

   let flat = nested.flatMap { $0.compactMap { $0 } } -> Option C

4. Quick Check:

   flatMap + compactMap unwraps and flattens non-nil values [OK]

Hint: Use compactMap inside flatMap to remove nils and flatten [OK]

Common Mistakes:

• Force unwrapping optionals causing runtime errors
• Filtering nil but not unwrapping optionals
• Flattening without removing nil values