CompactMap for optional unwrapping in Swift - Time & Space Complexity

Time Complexity: CompactMap for optional unwrapping

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code using compactMap changes as the input list grows.

Specifically, how does unwrapping optionals with compactMap affect performance?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

let numbers: [Int?] = [1, nil, 3, nil, 5]
let unwrapped = numbers.compactMap { $0 }
print(unwrapped)
    

This code takes an array of optional integers and creates a new array with only the non-nil values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The compactMap method loops through each element in the array once.
• How many times: It runs the closure once for every element in the input array.

How Execution Grows With Input

As the array gets bigger, the number of checks grows in direct proportion.

Input Size (n)	Approx. Operations
10	10 checks for nil and unwrap attempts
100	100 checks for nil and unwrap attempts
1000	1000 checks for nil and unwrap attempts

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of items in the array.

Common Mistake

[X] Wrong: "Using compactMap is slower because it does extra work to unwrap optionals."

[OK] Correct: compactMap only checks each item once, so it runs in linear time just like a simple loop.

Interview Connect

Understanding how compactMap works helps you explain efficient ways to handle optional values in arrays, a common task in Swift programming.

Self-Check

"What if we used map instead of compactMap? How would the time complexity change?"