Map use cases in Go - Time & Space Complexity

Time Complexity: Map use cases

O(n)

Understanding Time Complexity

Maps in Go help us store and find data quickly using keys. Understanding how fast these operations run is important when working with many items.

We want to know how the time to find or add items changes as the map grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func countWords(words []string) map[string]int {
    counts := make(map[string]int)
    for _, word := range words {
        counts[word]++
    }
    return counts
}
    

This code counts how many times each word appears in a list using a map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each word in the list and updating the map.
• How many times: Once for each word in the input list.

How Execution Grows With Input

Each word is processed once, and the map updates happen quickly on average regardless of size.

Input Size (n)	Approx. Operations
10	About 10 map updates
100	About 100 map updates
1000	About 1000 map updates

Pattern observation: The work grows directly with the number of words, not more or less.

Final Time Complexity

Time Complexity: O(n)

This means the time to count words grows in a straight line with the number of words.

Common Mistake

[X] Wrong: "Using a map makes the code run in constant time no matter how many words there are."

[OK] Correct: Each word still needs to be processed once, so time grows with the list size, not fixed.

Interview Connect

Knowing how maps work helps you explain efficient data lookups clearly, a useful skill in many coding tasks.

Self-Check

"What if we used a slice instead of a map to count words? How would the time complexity change?"

Practice

1. What is the primary use of a map in Go?

easy

A. To store data with keys for fast lookup

B. To perform mathematical calculations

C. To create user interfaces

D. To handle file input/output

Solution

1. Step 1: Understand the purpose of a map

   A map in Go is a collection of key-value pairs, designed for fast data retrieval using keys.

2. Step 2: Compare with other options

   Options B, C, and D describe unrelated tasks like calculations, UI, or file handling, which are not the main use of maps.

3. Final Answer:

   To store data with keys for fast lookup -> Option A

4. Quick Check:

   Maps = key-value storage [OK]

Hint: Maps store key-value pairs for quick access [OK]

Common Mistakes:

• Confusing maps with slices or arrays
• Thinking maps are for calculations
• Assuming maps handle UI or files

2. Which of the following is the correct way to create an empty map in Go?

easy

A. m := make([]string, 0)

B. var m map[string]int = make(map[string]int)

C. m := map[string]int

D. m := []int{}

Solution

1. Step 1: Identify map creation syntax

   In Go, maps are created using make(map[keyType]valueType). var m map[string]int = make(map[string]int) uses this correctly.

2. Step 2: Check other options

   m := []int{} creates a slice, not a map. m := map[string]int is invalid syntax for map creation. m := make([]string, 0) creates a slice, not a map.

3. Final Answer:

   var m map[string]int = make(map[string]int) -> Option B

4. Quick Check:

   Use make() to create maps [OK]

Hint: Use make() to create maps before use [OK]

Common Mistakes:

• Using slice syntax instead of map syntax
• Not using make() to initialize maps
• Confusing map and slice creation

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

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

medium

A. 8

B. 53

C. 0

D. Compilation error

Solution

1. Step 1: Understand map assignments

   The map m stores integers with string keys. "apple" maps to 5, "banana" maps to 3.

2. Step 2: Calculate the sum

   Adding m["apple"] + m["banana"] equals 5 + 3 = 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   5 + 3 = 8 [OK]

Hint: Sum values by accessing keys directly [OK]

Common Mistakes:

• Concatenating values as strings
• Expecting zero for existing keys
• Thinking code causes error

4. What is wrong with this Go code snippet?

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

medium

A. Cannot assign int values to map

B. Key "key" is invalid syntax

C. Map is not initialized with make() before use

D. fmt.Println cannot print map values

Solution

1. Step 1: Check map initialization

   The map m is declared but not initialized with make(). This causes a runtime panic on assignment.

2. Step 2: Understand consequences

   Without initialization, m["key"] = 10 causes a panic: assignment to nil map.

3. Final Answer:

   Map is not initialized with make() before use -> Option C

4. Quick Check:

   Initialize maps with make() [OK]

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

Common Mistakes:

• Forgetting to initialize map before use
• Assuming declaration is enough
• Misunderstanding map assignment rules

5. Given a map m := map[string]int{"a": 1, "b": 0, "c": 3}, which code snippet correctly checks if key "b" exists and its value is non-zero?

hard

A. if _, ok := m["b"]; ok { fmt.Println("Exists and non-zero") }

B. if m["b"] == 0 { fmt.Println("Exists and non-zero") }

C. if m["b"] >= 0 { fmt.Println("Exists and non-zero") }

D. if val, ok := m["b"]; ok && val != 0 { fmt.Println("Exists and non-zero") }

Solution

1. Step 1: Understand map key existence check

   Using val, ok := m["b"] lets us check if key "b" exists (ok) and get its value (val).

2. Step 2: Check value is non-zero

   The condition ok && val != 0 ensures key exists and value is not zero.

3. Final Answer:

   if val, ok := m["b"]; ok && val != 0 { fmt.Println("Exists and non-zero") } -> Option D

4. Quick Check:

   Check key existence and value together [OK]

Hint: Use val, ok := map[key] to check existence and value [OK]

Common Mistakes:

• Checking value without verifying key existence
• Assuming zero means key missing
• Using only ok without value check