Map creation in Go - Time & Space Complexity

Time Complexity: Map creation

O(n)

Understanding Time Complexity

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

We ask: How does adding items to a map affect the time needed?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func createMap(n int) map[int]int {
    m := make(map[int]int)
    for i := 0; i < n; i++ {
        m[i] = i * 2
    }
    return m
}

This code creates a map and adds n key-value pairs, where each key is an integer and the value is double the key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting a key-value pair into the map inside the loop.
• How many times: Exactly n times, once for each number from 0 to n-1.

How Execution Grows With Input

As n grows, the number of insertions grows the same way.

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

Pattern observation: The work 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 added.

Common Mistake

[X] Wrong: "Adding items to a map takes the same time no matter how many items are already there."

[OK] Correct: Each insertion takes some time, so more items mean more total time, even if each insert is fast.

Interview Connect

Understanding how map creation time grows helps you explain how data structures behave as they get bigger, a useful skill in many coding situations.

Self-Check

"What if we changed the map to store slices instead of integers? How would the time complexity change?"

Practice

1. What is the correct way to create an empty map with string keys and int values in Go?

easy

A. m := make(map[string]int)

B. m := map[string]int()

C. m := new(map[string]int)

D. m := []string{}

Solution

1. Step 1: Understand map creation syntax

   In Go, the built-in function make is used to create maps with specified key and value types.

2. Step 2: Identify the correct syntax for an empty map

   make(map[string]int) creates an empty map with string keys and int values.

3. Final Answer:

   m := make(map[string]int) -> Option A

4. Quick Check:

   Use make(map[keyType]valueType) to create maps [OK]

Hint: Use make() with map[keyType]valueType to create maps [OK]

Common Mistakes:

• Using new() instead of make() for maps
• Trying to create map with slice syntax
• Confusing map literal with empty slice

2. Which of the following is a syntax error when creating a map in Go?

easy

A. m := make(map[int]string)

B. m := make(map[float64]int)

C. m := make(map[[]int]string)

D. m := map[int]string{}

Solution

1. Step 1: Check key type validity

   Map keys must be comparable types. Slices ([]int) are not comparable in Go.

2. Step 2: Identify invalid map key type

   Using []int as a key type causes a syntax error because slices cannot be map keys.

3. Final Answer:

   m := make(map[[]int]string) -> Option C

4. Quick Check:

   Map keys must be comparable types [OK]

Hint: Map keys cannot be slices or maps, only comparable types [OK]

Common Mistakes:

• Using slices or maps as map keys
• Confusing map literal with slice literal
• Ignoring key type restrictions

3. What will be the output of the following Go code?

m := make(map[string]int)
m["apple"] = 5
m["banana"] = 3
fmt.Println(m["apple"] + m["banana"])

medium

A. 53

B. 8

C. 0

D. Compilation error

Solution

1. Step 1: Understand map assignments

   The map m stores key-value pairs: "apple"=5 and "banana"=3.

2. Step 2: Calculate the sum of values

   Adding m["apple"] (5) and m["banana"] (3) results in 8.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   5 + 3 = 8 [OK]

Hint: Sum map values by accessing keys directly [OK]

Common Mistakes:

• Concatenating values as strings instead of adding
• Expecting zero for existing keys
• Forgetting to initialize map before use

4. Identify the error in the following Go code snippet:

var m map[string]int
m["key"] = 10
fmt.Println(m["key"])

medium

A. No error, prints 10

B. Syntax error in map declaration

C. Key type must be int, not string

D. Map declared but not initialized, causes runtime panic

Solution

1. Step 1: Check map initialization

   The map m is declared but not initialized with make, so it is nil.

2. Step 2: Understand runtime behavior

   Assigning to a nil map causes a runtime panic (error) because the map is not ready to store values.

3. Final Answer:

   Map declared but not initialized, causes runtime panic -> Option D

4. Quick Check:

   Declare + make before use to avoid panic [OK]

Hint: Always initialize maps with make() before adding keys [OK]

Common Mistakes:

• Forgetting to initialize map before assignment
• Assuming declaration alone creates usable map
• Confusing map declaration with slice declaration

5. Given a slice of strings keys := []string{"a", "b", "c"} and a slice of ints values := []int{1, 2, 3}, which code snippet correctly creates a map from keys to values?

hard

A. m := make(map[string]int)
for i := range keys {
m[keys[i]] = values[i]
}

B. m := map[string]int{}
for i, v := range values {
m[v] = keys[i]
}

C. m := make(map[int]string)
for i := 0; i < len(keys); i++ {
m[i] = keys[i]
}

D. m := make(map[string]int)
for i := 0; i < len(values); i++ {
m[values[i]] = keys[i]
}

Solution

1. Step 1: Match keys and values correctly

   Keys are strings, values are ints. The map must have type map[string]int.

2. Step 2: Verify loop and assignment

   m := make(map[string]int) for i := range keys { m[keys[i]] = values[i] } loops over keys and assigns m[keys[i]] = values[i], correctly pairing keys to values.

3. Final Answer:

   m := make(map[string]int) for i := range keys { m[keys[i]] = values[i] } -> Option A

4. Quick Check:

   Loop keys, assign values to map[key] [OK]

Hint: Loop keys, assign values to map[key] for correct pairing [OK]

Common Mistakes:

• Swapping keys and values in map assignment
• Using wrong map key or value types
• Not initializing map before assignment