Sequence operators (map, filter) in Kotlin - Time & Space Complexity

Time Complexity: Sequence operators (map, filter)

O(n)

Understanding Time Complexity

We want to understand how long it takes to process a list using sequence operators like map and filter.

How does the time grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf(1, 2, 3, 4, 5)
val result = numbers
    .filter { it % 2 == 0 }
    .map { it * 2 }

This code filters even numbers from a list and then doubles each filtered number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The filter and map each go through the list once.
• How many times: Each element is checked once in filter, then each filtered element is processed once in map.

How Execution Grows With Input

As the list size grows, the number of operations grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 20 (10 for filter + up to 10 for map)
100	About 200 (100 for filter + up to 100 for map)
1000	About 2000 (1000 for filter + up to 1000 for map)

Pattern observation: The total work grows roughly twice the input size, so it grows linearly.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly in proportion to the list size.

Common Mistake

[X] Wrong: "Using both filter and map means the time grows like n squared because there are two steps."

[OK] Correct: Each step goes through the list once, so the total time adds up, not multiplies, keeping growth linear.

Interview Connect

Understanding how sequence operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we chained three sequence operations instead of two? How would the time complexity change?"

Practice

1. What does the map operator do in a Kotlin sequence?

easy

A. It removes items that do not match a condition.

B. It transforms each item in the sequence to a new value.

C. It sorts the items in the sequence.

D. It counts the number of items in the sequence.

Solution

1. Step 1: Understand the purpose of map

   The map operator applies a function to each item, changing it to a new value.

2. Step 2: Compare with other operators

   filter removes items, sort orders items, and count counts items, so these are different.

3. Final Answer:

   It transforms each item in the sequence to a new value. -> Option B

4. Quick Check:

   map = transform each item [OK]

Hint: Map changes items; filter removes items [OK]

Common Mistakes:

• Confusing map with filter
• Thinking map sorts or counts items
• Assuming map removes items

2. Which of the following is the correct syntax to filter even numbers from a sequence seq in Kotlin?

easy

A. seq.filter { it % 2 == 0 }

B. seq.map { it % 2 == 0 }

C. seq.filter(it % 2 == 0)

D. seq.map { it / 2 == 0 }

Solution

1. Step 1: Identify correct filter syntax

   In Kotlin, filter takes a lambda with condition inside curly braces: { it % 2 == 0 }.

2. Step 2: Check other options

   map changes values, not filters; seq.filter(it % 2 == 0) misses braces; seq.map { it / 2 == 0 } uses wrong condition.

3. Final Answer:

   seq.filter { it % 2 == 0 } -> Option A

4. Quick Check:

   filter uses braces and condition [OK]

Hint: filter uses braces with condition inside [OK]

Common Mistakes:

• Using map instead of filter
• Missing curly braces in lambda
• Wrong condition inside lambda

3. What is the output of this Kotlin code?

val numbers = sequenceOf(1, 2, 3, 4)
val result = numbers.filter { it % 2 == 0 }.map { it * 10 }.toList()
println(result)

medium

A. [10, 20]

B. [2, 4]

C. [20, 40]

D. [1, 3]

Solution

1. Step 1: Apply filter to keep even numbers

   Filter keeps numbers where it % 2 == 0, so 2 and 4 remain.

2. Step 2: Apply map to multiply each by 10

   Mapping multiplies each by 10: 2 * 10 = 20, 4 * 10 = 40.

3. Final Answer:

   [20, 40] -> Option C

4. Quick Check:

   filter evens then map *10 = [20, 40] [OK]

Hint: Filter first, then map transforms filtered items [OK]

Common Mistakes:

• Mapping before filtering
• Confusing filter condition
• Forgetting to convert sequence to list

4. Find the error in this Kotlin code snippet:

val seq = sequenceOf(1, 2, 3, 4)
val filtered = seq.filter(it % 2 == 0)
println(filtered.toList())

medium

A. Missing curly braces around lambda in filter

B. Using map instead of filter

C. Sequence cannot be converted to list

D. Filter condition should be it % 2 != 0

Solution

1. Step 1: Check filter lambda syntax

   Filter requires a lambda with curly braces: { it % 2 == 0 }. The code misses braces.

2. Step 2: Validate other options

   Map is not used here; sequence can convert to list; condition can be any boolean expression.

3. Final Answer:

   Missing curly braces around lambda in filter -> Option A

4. Quick Check:

   filter needs braces for lambda [OK]

Hint: Always use braces {} for lambdas in filter [OK]

Common Mistakes:

• Omitting braces in lambda
• Confusing filter and map
• Wrong filter condition assumed as error

5. Given a sequence of strings seq = sequenceOf("apple", "banana", "cherry", "date"), which Kotlin code correctly filters strings containing letter 'a' and converts them to uppercase?

hard

A. seq.filter { it.contains('a') }.map { it.lowercase() }.toList()

B. seq.map { it.uppercase() }.filter { it.contains('a') }.toList()

C. seq.map { it.lowercase() }.filter { it.contains('a') }.toList()

D. seq.filter { it.contains('a') }.map { it.uppercase() }.toList()

Solution

1. Step 1: Filter strings containing 'a'

   Use filter { it.contains('a') } to keep only strings with 'a'. This keeps "apple", "banana", "date".

2. Step 2: Convert filtered strings to uppercase

   Use map { it.uppercase() } to change these strings to uppercase.

3. Final Answer:

   seq.filter { it.contains('a') }.map { it.uppercase() }.toList() -> Option D

4. Quick Check:

   Filter then map uppercase = seq.filter { it.contains('a') }.map { it.uppercase() }.toList() [OK]

Hint: Filter first, then map to uppercase [OK]

Common Mistakes:

• Mapping before filtering changes all strings
• Using lowercase instead of uppercase
• Filtering after mapping changes string case before filter