Map creation (mapOf, mutableMapOf) in Kotlin - Time & Space Complexity

Time Complexity: Map creation (mapOf, mutableMapOf)

O(n)

Understanding Time Complexity

When we create a map in Kotlin, the program needs to add each item one by one. Understanding how the time needed grows as we add more items helps us write better code.

We want to know: How does the time to create a map change when we add more entries?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf("one" to 1, "two" to 2, "three" to 3)
val map = mutableMapOf()
for ((key, value) in numbers) {
    map[key] = value
}
    

This code creates a mutable map and adds each pair from a list into it one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each key-value pair to the map inside the loop.
• How many times: Once for every item in the input list.

How Execution Grows With Input

Each new item means one more add operation. So if you double the items, you double the work.

Input Size (n)	Approx. Operations
10	10 adds
100	100 adds
1000	1000 adds

Pattern observation: The time grows directly with the number of items added.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the map grows in a straight line with the number of items you add.

Common Mistake

[X] Wrong: "Adding items to a map is instant no matter how many items there are."

[OK] Correct: Each item still needs to be placed inside the map, so more items mean more work and more time.

Interview Connect

Knowing how map creation time grows helps you explain your code choices clearly and shows you understand how data structures work behind the scenes.

Self-Check

"What if we used a mapOf() with all items at once instead of adding them one by one? How would the time complexity change?"

Practice

1. What does mapOf create in Kotlin?

easy

A. A list of values without keys

B. A mutable map that can be changed later

C. A fixed map that cannot be changed after creation

D. An empty map with no keys or values

Solution

1. Step 1: Understand mapOf purpose

   mapOf creates a map with key-value pairs that cannot be modified after creation.

2. Step 2: Compare with other map types

   mutableMapOf allows changes, but mapOf does not.

3. Final Answer:

   A fixed map that cannot be changed after creation -> Option C

4. Quick Check:

   mapOf = fixed map [OK]

Hint: Remember: mapOf = fixed map, mutableMapOf = changeable map [OK]

Common Mistakes:

• Confusing mapOf with mutableMapOf
• Thinking mapOf creates an empty map
• Assuming mapOf allows adding new entries

2. Which of the following is the correct syntax to create a mutable map with keys "a" and "b" and values 1 and 2 respectively?

easy

A. val map = mutableMapOf("a" to 1, "b" to 2)

B. val map = mapOf("a" -> 1, "b" -> 2)

C. val map = mutableMapOf("a" = 1, "b" = 2)

D. val map = mapOf("a" to 1, "b" to 2)

Solution

1. Step 1: Identify correct syntax for mutableMapOf

   The correct syntax uses mutableMapOf with pairs using to keyword.

2. Step 2: Check each option

   val map = mutableMapOf("a" to 1, "b" to 2) uses mutableMapOf and to correctly. val map = mapOf("a" -> 1, "b" -> 2) uses wrong arrow ->. val map = mutableMapOf("a" = 1, "b" = 2) uses = which is invalid here. val map = mapOf("a" to 1, "b" to 2) uses mapOf which creates an immutable map.

3. Final Answer:

   val map = mutableMapOf("a" to 1, "b" to 2) -> Option A

4. Quick Check:

   mutableMapOf + to = correct syntax [OK]

Hint: Use mutableMapOf with "key" to value pairs [OK]

Common Mistakes:

• Using -> instead of to for pairs
• Using = inside mapOf or mutableMapOf
• Confusing mapOf and mutableMapOf

3. What is the output of this Kotlin code?

val map = mapOf("x" to 10, "y" to 20)
println(map["x"])
println(map["z"])

medium

A. 20
null

B. 10
null

C. null
null

D. 10
0

Solution

1. Step 1: Access existing key "x"

   map["x"] returns 10 because "x" is a key with value 10.

2. Step 2: Access non-existing key "z"

   map["z"] returns null because "z" is not in the map.

3. Final Answer:

   10\nnull -> Option B

4. Quick Check:

   Existing key returns value, missing key returns null [OK]

Hint: map[key] returns value or null if key missing [OK]

Common Mistakes:

• Expecting 0 instead of null for missing key
• Confusing values of different keys
• Assuming map is mutable and can add keys

4. What is wrong with this Kotlin code?

val map = mapOf("a" to 1)
map["b"] = 2

medium

A. mapOf creates an immutable map, so you cannot add new entries

B. The syntax for adding entries is incorrect; should use put()

C. Keys must be integers, not strings

D. mapOf requires mutableMapOf to add entries

Solution

1. Step 1: Understand mapOf immutability

   mapOf creates an immutable map that cannot be changed after creation.

2. Step 2: Adding entries to immutable map causes error

   Trying to assign a new key-value pair with map["b"] = 2 causes a compile-time error because the map is immutable.

3. Final Answer:

   mapOf creates an immutable map, so you cannot add new entries -> Option A

4. Quick Check:

   Immutable map cannot be changed [OK]

Hint: Use mutableMapOf to add or change entries [OK]

Common Mistakes:

• Trying to add entries to mapOf
• Using wrong syntax for adding entries
• Confusing mutableMapOf and mapOf

5. You want to create a map that stores student names as keys and their scores as values. You also want to update scores later. Which Kotlin code snippet correctly achieves this?

hard

A. val scores = mutableMapOf("Alice" to 90, "Bob" to 85)
scores.add("Alice", 95)

B. val scores = mapOf("Alice" to 90, "Bob" to 85)
scores["Alice"] = 95

C. val scores = mapOf("Alice" to 90, "Bob" to 85)
scores.put("Alice", 95)

D. val scores = mutableMapOf("Alice" to 90, "Bob" to 85)
scores["Alice"] = 95

Solution

1. Step 1: Choose a mutable map to allow updates

   Since scores need to be updated, mutableMapOf is required.

2. Step 2: Use correct method to update value

   Assigning with scores["Alice"] = 95 correctly updates the value in a mutable map.

3. Step 3: Check other options for errors

   val scores = mapOf("Alice" to 90, "Bob" to 85) scores["Alice"] = 95 uses immutable map and tries to update, causing error. val scores = mapOf("Alice" to 90, "Bob" to 85) scores.put("Alice", 95) tries to use put on immutable map, error. val scores = mutableMapOf("Alice" to 90, "Bob" to 85) scores.add("Alice", 95) uses non-existent add method.

4. Final Answer:

   val scores = mutableMapOf("Alice" to 90, "Bob" to 85) scores["Alice"] = 95 -> Option D

5. Quick Check:

   mutableMapOf + assignment updates map [OK]

Hint: Use mutableMapOf and bracket assignment to update entries [OK]

Common Mistakes:

• Using mapOf when updates are needed
• Trying to use put on immutable map
• Using add method which does not exist