Flat_map for nested flattening in Ruby - Time & Space Complexity

Time Complexity: Flat_map for nested flattening

O(n)

Understanding Time Complexity

We want to understand how the time it takes to flatten nested lists using flat_map grows as the input gets bigger.

Specifically, how does the number of operations change when we use flat_map on nested arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

nested = [[1, 2], [3, 4], [5, 6]]
flat = nested.flat_map { |sub_array| sub_array.map { |x| x * 2 } }

This code doubles each number inside nested arrays and flattens the result into one array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Iterating over each sub-array and then each element inside it.
• How many times: For each element in all nested arrays combined, the block runs once.

How Execution Grows With Input

As the total number of elements inside all nested arrays grows, the work grows roughly the same amount.

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

Pattern observation: The operations grow linearly with the total number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to flatten and process grows directly in proportion to the total number of elements.

Common Mistake

[X] Wrong: "Using flat_map is slower because it has to flatten, so it must be more than linear time."

[OK] Correct: The flattening happens as part of one pass over all elements, so it still only touches each element once, keeping the time linear.

Interview Connect

Understanding how flat_map works helps you explain how nested data can be handled efficiently, a useful skill in many coding tasks.

Self-Check

What if we replaced flat_map with separate map and flatten calls? How would the time complexity change?

Practice

1. What does the Ruby method flat_map do when applied to an array of arrays?

easy

A. It removes duplicate elements from the array.

B. It only flattens the array without applying any block.

C. It applies a block to each element and flattens the result by one level.

D. It maps elements but keeps the nested structure intact.

Solution

1. Step 1: Understand flat_map behavior

   The flat_map method applies a block to each element of the array.

2. Step 2: Flatten the mapped results

   After mapping, it flattens the resulting array by one level, combining nested arrays into a single array.

3. Final Answer:

   It applies a block to each element and flattens the result by one level. -> Option C

4. Quick Check:

   flat_map = map + flatten(1) [OK]

Hint: Remember: flat_map = map + flatten one level [OK]

Common Mistakes:

• Thinking flat_map flattens all nested levels
• Confusing flat_map with flatten
• Assuming flat_map does not apply a block

2. Which of the following is the correct syntax to use flat_map on an array arr to double each number?

easy

A. arr.flat_map do x * 2 end

B. arr.flat_map { |x| [x * 2] }

C. arr.flat_map { x * 2 }

D. arr.flat_map(x) { x * 2 }

Solution

1. Step 1: Understand flat_map block return

   The block given to flat_map should return an array or enumerable to flatten.

2. Step 2: Check each option's block return

   arr.flat_map { |x| [x * 2] } returns an array [x * 2], which flat_map will flatten by one level, producing a flat array of doubled values.

3. Final Answer:

   arr.flat_map { |x| [x * 2] } -> Option B

4. Quick Check:

   Block must return array for flat_map flattening [OK]

Hint: Return an array inside block for flat_map to flatten [OK]

Common Mistakes:

• Returning a single value instead of an array in block
• Using incorrect block syntax
• Passing arguments incorrectly to flat_map

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

arr = [[1, 2], [3, 4]]
result = arr.flat_map { |sub| sub.map { |x| x * 2 } }
puts result.inspect

medium

A. [2, 4, 6, 8]

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

C. [1, 2, 3, 4]

D. [[1, 2], [3, 4]]

Solution

1. Step 1: Inner map doubles each element

   For each sub-array, sub.map { |x| x * 2 } creates a new array with doubled values: [2,4] and [6,8].

2. Step 2: flat_map flattens one level

   flat_map combines these arrays into a single flat array: [2, 4, 6, 8].

3. Final Answer:

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

4. Quick Check:

   flat_map flattens mapped arrays one level [OK]

Hint: flat_map flattens one level after mapping [OK]

Common Mistakes:

• Expecting nested arrays in output
• Confusing map with flat_map output
• Ignoring inner map doubling

4. Identify the error in this Ruby code snippet:

arr = [1, 2, 3, 4]
result = arr.flat_map { |x| x * 2 }
puts result.inspect

medium

A. flat_map cannot be called on nested arrays.

B. The variable 'result' is not assigned properly.

C. The syntax of the block is incorrect.

D. flat_map block returns integers, not arrays, so flattening fails.

Solution

1. Step 1: Analyze block return values

   The block { |x| x * 2 } returns integers, not arrays or enumerables.

2. Step 2: Understand flat_map flattening requirement

   flat_map expects the block to return arrays or enumerables to flatten one level; returning integers causes flattening to fail or unexpected results.

3. Final Answer:

   flat_map block returns integers, not arrays, so flattening fails. -> Option D

4. Quick Check:

   Block must return arrays for flat_map flattening [OK]

Hint: Block must return arrays, not single values, for flat_map [OK]

Common Mistakes:

• Returning single values instead of arrays in block
• Assuming flat_map works like map without flattening
• Misunderstanding flat_map usage on nested arrays

5. Given a nested array of words grouped by their first letter, how can you use flat_map to get a flat array of all words in uppercase?

words = [['apple', 'apricot'], ['banana', 'blueberry'], ['cherry']]
# Fill in the blank:
result = words.flat_map { |group| ________ }
puts result.inspect

hard

A. group.map { |w| w.upcase }

B. group.upcase

C. group.map { w.upcase }

D. group.flat_map { w.upcase }

Solution

1. Step 1: Map each word to uppercase inside each group

   Use group.map { |w| w.upcase } to convert each word in the sub-array to uppercase.

2. Step 2: Use flat_map to flatten the mapped arrays

   flat_map will flatten the arrays of uppercase words into a single flat array.

3. Final Answer:

   group.map { |w| w.upcase } -> Option A

4. Quick Check:

   flat_map + map for nested uppercase flattening [OK]

Hint: Use map inside flat_map block to transform and flatten [OK]

Common Mistakes:

• Calling upcase on array instead of strings
• Using flat_map inside block unnecessarily
• Returning non-array values from block