Map transformation in Kotlin - Time & Space Complexity

Time Complexity: Map transformation

O(n)

Understanding Time Complexity

When we transform a map, we want to know how the time it takes changes as the map gets bigger.

We ask: How does the work grow when the map has more entries?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val originalMap = mapOf("a" to 1, "b" to 2, "c" to 3)
val transformedMap = originalMap.mapValues { (key, value) -> value * 2 }
println(transformedMap)
    

This code takes each entry in the map and doubles its value, creating a new map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The mapValues function visits each key-value pair once.
• How many times: Exactly once for each entry in the map.

How Execution Grows With Input

As the map gets bigger, the work grows in a straight line with the number of entries.

Input Size (n)	Approx. Operations
10	10 visits to entries
100	100 visits to entries
1000	1000 visits to entries

Pattern observation: Doubling the number of entries doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to transform the map grows directly with the number of entries.

Common Mistake

[X] Wrong: "Transforming a map is instant no matter the size."

[OK] Correct: Each entry must be visited once, so bigger maps take more time.

Interview Connect

Understanding how map transformations scale helps you write efficient code and explain your choices clearly.

Self-Check

What if we used mapKeys instead of mapValues? How would the time complexity change?

Practice

1. What does the map function do when applied to a list in Kotlin?

easy

A. It removes elements from the list based on a condition.

B. It creates a new list by applying a transformation to each element.

C. It sorts the list in ascending order.

D. It changes the original list by modifying its elements.

Solution

1. Step 1: Understand the purpose of map

   The map function applies a given transformation to each element of the list.

2. Step 2: Check the effect on the list

   It returns a new list with transformed elements without changing the original list.

3. Final Answer:

   It creates a new list by applying a transformation to each element. -> Option B

4. Quick Check:

   map transforms each item and returns new list [OK]

Hint: Remember: map returns a new list, original stays same [OK]

Common Mistakes:

• Thinking map modifies the original list
• Confusing map with filter or sort
• Assuming map removes elements

2. Which of the following is the correct syntax to transform a list of integers by doubling each value using map in Kotlin?

easy

A. val result = list.map { it * 2 }

B. val result = list.map(it * 2)

C. val result = list.map -> it * 2

D. val result = list.map { it + 2 }

Solution

1. Step 1: Identify correct lambda syntax

   The map function requires a lambda inside curly braces: { it * 2 }.

2. Step 2: Check the transformation logic

   Doubling means multiplying by 2, so it * 2 is correct.

3. Final Answer:

   val result = list.map { it * 2 } -> Option A

4. Quick Check:

   Correct lambda syntax with doubling [OK]

Hint: Use curly braces and 'it' for lambda in map [OK]

Common Mistakes:

• Missing curly braces around lambda
• Using parentheses instead of braces
• Wrong operation inside lambda

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

val numbers = listOf(1, 2, 3)
val result = numbers.map { it + 5 }
println(result)

medium

A. [6, 7, 8]

B. [1, 2, 3, 5]

C. [5, 6, 7]

D. [1, 2, 3]

Solution

1. Step 1: Apply the map transformation

   Each element in numbers is increased by 5: 1+5=6, 2+5=7, 3+5=8.

2. Step 2: Form the new list

   The new list is [6, 7, 8], which is printed.

3. Final Answer:

   [6, 7, 8] -> Option A

4. Quick Check:

   Each number +5 = [6, 7, 8] [OK]

Hint: Add 5 to each element inside map to get output [OK]

Common Mistakes:

• Confusing original list with transformed list
• Adding 5 only once instead of to each element
• Misreading the output format

4. Identify the error in this Kotlin code snippet:

val list = listOf(1, 2, 3)
val newList = list.map(it * 3)
println(newList)

medium

A. The multiplication operator is incorrect.

B. Using map on a list is not allowed.

C. The list should be mutable to use map.

D. Missing curly braces around the lambda expression.

Solution

1. Step 1: Check lambda syntax in map

   The map function requires a lambda inside curly braces, but here parentheses are used without braces.

2. Step 2: Confirm correct usage

   Correct syntax is list.map { it * 3 } to apply multiplication.

3. Final Answer:

   Missing curly braces around the lambda expression. -> Option D

4. Quick Check:

   Lambda needs braces in map [OK]

Hint: Always use curly braces for lambda in map [OK]

Common Mistakes:

• Using parentheses instead of braces for lambda
• Thinking map needs mutable list
• Misunderstanding operator usage

5. Given a list of strings val words = listOf("apple", "banana", "cherry"), how can you create a map where each word is a key and its length is the value using Kotlin's map transformation?

hard

A. val wordLengths = words.associateWith { it.length }

B. val wordLengths = words.map { it.length to it }

C. val wordLengths = words.map { it to it.length } .toMap()

D. val wordLengths = words.map { it.length }

Solution

1. Step 1: Understand the goal

   We want a map where keys are words and values are their lengths.

2. Step 2: Use map to create pairs and convert to map

   words.map { it to it.length } creates pairs (word, length). Then toMap() converts the list of pairs to a map.

3. Final Answer:

   val wordLengths = words.map { it to it.length } .toMap() -> Option C

4. Quick Check:

   Map pairs then convert to map [OK]

Hint: Use map to pairs and then toMap() for map creation [OK]

Common Mistakes:

• Using associateWith is correct but not the asked map transformation
• Mapping only lengths returns list, not map
• Swapping key and value in pairs