Map, filter, reduce patterns in Swift - Time & Space Complexity

Time Complexity: Map, filter, reduce patterns

O(n)

Understanding Time Complexity

When using map, filter, and reduce in Swift, it's important to know how the time to run grows as the input list gets bigger.

We want to see how many steps these patterns take when working on arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

let numbers = [1, 2, 3, 4, 5]

let doubled = numbers.map { $0 * 2 }
let evens = numbers.filter { $0 % 2 == 0 }
let sum = numbers.reduce(0) { $0 + $1 }
    

This code doubles each number, selects even numbers, and sums all numbers in the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each pattern loops through the entire array once.
• How many times: Each element is visited exactly one time per pattern.

How Execution Grows With Input

As the array gets bigger, the number of steps grows in a straight line with the number of elements.

Input Size (n)	Approx. Operations
10	About 10 steps per pattern
100	About 100 steps per pattern
1000	About 1000 steps per pattern

Pattern observation: The work grows evenly as the input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly with the number of items in the array.

Common Mistake

[X] Wrong: "Using map, filter, and reduce together means the time is multiplied and becomes much slower."

[OK] Correct: Each pattern goes through the array once, so doing them one after another adds their times, but each is still just one pass through the data.

Interview Connect

Understanding how these patterns scale helps you explain your code clearly and shows you know how to write efficient Swift code.

Self-Check

"What if we combined map and filter into one loop? How would the time complexity change?"

Practice

1. What does the map function do in Swift when applied to an array?

easy

A. It changes each item in the array based on a rule.

B. It removes items that don't match a condition.

C. It combines all items into a single value.

D. It sorts the array in ascending order.

Solution

1. Step 1: Understand the purpose of map

   The map function applies a transformation to each element in the array, creating a new array with the changed items.

2. Step 2: Compare with other functions

   Unlike filter which removes items, or reduce which combines items, map changes each item individually.

3. Final Answer:

   It changes each item in the array based on a rule. -> Option A

4. Quick Check:

   map = change each item [OK]

Hint: Map transforms every item, filter picks, reduce combines [OK]

Common Mistakes:

• Confusing map with filter or reduce
• Thinking map removes items
• Assuming map combines items into one

2. Which of the following is the correct syntax to use filter on an array numbers to keep only even numbers?

easy

A. let evens = numbers.map { $0 % 2 == 0 }

B. let evens = numbers.filter($0 % 2 == 0)

C. let evens = numbers.reduce(0) { $0 % 2 == 0 }

D. let evens = numbers.filter { $0 % 2 == 0 }

Solution

1. Step 1: Identify correct filter syntax

   The filter method uses a closure with a condition inside curly braces, like { $0 % 2 == 0 }, to keep items matching the condition.

2. Step 2: Check each option

   let evens = numbers.filter { $0 % 2 == 0 } correctly uses filter with the closure. let evens = numbers.map { $0 % 2 == 0 } uses map which changes items, not filters. let evens = numbers.reduce(0) { $0 % 2 == 0 } misuses reduce. let evens = numbers.filter($0 % 2 == 0) misses the closure braces.

3. Final Answer:

   let evens = numbers.filter { $0 % 2 == 0 } -> Option D

4. Quick Check:

   filter syntax = filter { condition } [OK]

Hint: Filter needs braces and a condition inside { } [OK]

Common Mistakes:

• Using map instead of filter
• Omitting braces in closure
• Using reduce incorrectly for filtering

3. What is the output of this Swift code?

let numbers = [1, 2, 3, 4]
let result = numbers.reduce(0) { $0 + $1 }
print(result)

medium

A. 0

B. [1, 2, 3, 4]

C. 10

D. Error

Solution

1. Step 1: Understand reduce with initial value 0

   The reduce starts with 0 and adds each number in the array: 0 + 1 + 2 + 3 + 4.

2. Step 2: Calculate the sum

   Adding all numbers: 0 + 1 = 1, 1 + 2 = 3, 3 + 3 = 6, 6 + 4 = 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Sum of [1,2,3,4] = 10 [OK]

Hint: Reduce with + sums all items starting from initial value [OK]

Common Mistakes:

• Confusing reduce with map or filter output
• Forgetting initial value in reduce
• Expecting array output instead of single value

4. Identify the error in this Swift code snippet:

let words = ["apple", "banana", "cherry"]
let filtered = words.filter { word in
    word.count > 5
}
print(filtered)

medium

A. No error, code runs correctly

B. Incorrect use of filter instead of map

C. Using word.count instead of word.length

D. Missing return keyword inside filter closure

Solution

1. Step 1: Check filter closure syntax

   The closure uses implicit return because it is a single expression, so no explicit return is needed.

2. Step 2: Verify property usage

   word.count is the correct way to get string length in Swift, so no error there.

3. Final Answer:

   No error, code runs correctly -> Option A

4. Quick Check:

   Single-expression closures return implicitly [OK]

Hint: Single-expression closures return automatically, no return needed [OK]

Common Mistakes:

• Adding unnecessary return keyword
• Confusing count with length property
• Thinking filter needs map syntax

5. Given an array of integers, how would you use map, filter, and reduce together to find the sum of squares of only the odd numbers? Choose the correct Swift code.

hard

A. let sum = numbers.map { $0 * $0 }.filter { $0 % 2 != 0 }.reduce(0, +)

B. let sum = numbers.filter { $0 % 2 != 0 }.map { $0 * $0 }.reduce(0, +)

C. let sum = numbers.reduce(0) { $0 + $1 * $1 }

D. let sum = numbers.filter { $0 % 2 == 0 }.map { $0 * $0 }.reduce(0, +)

Solution

1. Step 1: Filter odd numbers first

   We want only odd numbers, so use filter { $0 % 2 != 0 } to keep them.

2. Step 2: Map to square each odd number

   Use map { $0 * $0 } to get squares of the filtered odd numbers.

3. Step 3: Reduce to sum all squares

   Use reduce(0, +) to add all squared values into one sum.

4. Final Answer:

   let sum = numbers.filter { $0 % 2 != 0 }.map { $0 * $0 }.reduce(0, +) -> Option B

5. Quick Check:

   Filter odds, map squares, reduce sum [OK]

Hint: Filter odds first, then map squares, finally reduce sum [OK]

Common Mistakes:

• Mapping before filtering odd numbers
• Filtering even numbers by mistake
• Using reduce without mapping squares