Accessing map values in Go - Time & Space Complexity

Time Complexity: Accessing map values

O(1)

Understanding Time Complexity

When we access values in a map, we want to know how long it takes as the map grows.

We ask: How does the time to get a value change when the map has more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func getValue(m map[string]int, key string) int {
    return m[key]
}

This code returns the value for a given key from a map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Direct lookup of a key in the map.
• How many times: Exactly once per call.

How Execution Grows With Input

Looking up a key takes about the same time no matter how many items are in the map.

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

Pattern observation: The time stays roughly the same as the map grows.

Final Time Complexity

Time Complexity: O(1)

This means accessing a value by key takes about the same time no matter how big the map is.

Common Mistake

[X] Wrong: "Looking up a key takes longer if the map has more items."

[OK] Correct: Maps use a system that finds keys quickly, so the time does not grow with size.

Interview Connect

Understanding how map lookups work helps you explain why your code stays fast even with lots of data.

Self-Check

"What if the map used a list instead of a hash? How would the time complexity change?"

Practice

1. What does the expression value, ok := myMap["key"] do in Go?

easy

A. It retrieves the value for "key" and checks if the key exists in the map.

B. It deletes the key "key" from the map.

C. It adds a new key "key" with value "ok" to the map.

D. It returns the number of keys in the map.

Solution

1. Step 1: Understand map access syntax

   In Go, value, ok := myMap["key"] retrieves the value for the key and a boolean indicating if the key exists.

2. Step 2: Explain the boolean ok

   The ok is true if the key is present, false otherwise.

3. Final Answer:

   It retrieves the value for "key" and checks if the key exists in the map. -> Option A

4. Quick Check:

   Map access with existence check = value, ok [OK]

Hint: Remember: value, ok checks key presence in map [OK]

Common Mistakes:

• Thinking it deletes the key
• Assuming it adds a key
• Confusing it with map length

2. Which of the following is the correct way to check if a key exists in a Go map named m for key k?

easy

A. value, ok := m[k]; if ok { ... }

B. value := m[k]; if value != nil { ... }

C. if m.contains(k) { ... }

D. if m[k] != 0 { ... }

Solution

1. Step 1: Recall Go map existence check syntax

   In Go, to check if a key exists, use value, ok := m[k] and then check ok.

2. Step 2: Analyze options

   value := m[k]; if value != nil { ... } wrongly assumes value is nil for missing keys, which is not always true. if m.contains(k) { ... } uses a method that does not exist. if m[k] != 0 { ... } checks value but zero value can be valid.

3. Final Answer:

   value, ok := m[k]; if ok { ... } -> Option A

4. Quick Check:

   Use value, ok to check key presence [OK]

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

Common Mistakes:

• Checking value against nil or zero instead of ok
• Using non-existent map methods
• Assuming zero value means key missing

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

m := map[string]int{"a": 10, "b": 20}
value, ok := m["c"]
fmt.Println(value, ok)

medium

A. Compilation error

B. 0 true

C. 20 true

D. 0 false

Solution

1. Step 1: Understand map lookup for missing key

   Key "c" is not in map m, so value gets zero value for int, which is 0, and ok is false.

2. Step 2: Print output values

   Printing value and ok prints "0 false".

3. Final Answer:

   0 false -> Option D

4. Quick Check:

   Missing key returns zero value and false [OK]

Hint: Missing map keys return zero value and false [OK]

Common Mistakes:

• Assuming missing key returns true
• Expecting runtime error for missing key
• Confusing zero value with actual stored value

4. Identify the error in this Go code snippet:

m := map[string]int{"x": 5}
value := m["y"]
if value {
    fmt.Println("Key exists")
}

medium

A. Missing declaration of map m.

B. Map key "y" does not exist, causing runtime panic.

C. Cannot use int value as boolean in if condition.

D. Syntax error in map initialization.

Solution

1. Step 1: Analyze the if condition

   The variable value is an int, but Go requires a boolean expression in if conditions.

2. Step 2: Understand Go type rules

   Using an int directly as a boolean causes a compile-time error.

3. Final Answer:

   Cannot use int value as boolean in if condition. -> Option C

4. Quick Check:

   if conditions need boolean, not int [OK]

Hint: if needs boolean, not int value [OK]

Common Mistakes:

• Assuming missing key causes panic
• Ignoring type mismatch in if condition
• Thinking map declaration is missing

5. Given a map m := map[string]int{"a": 1, "b": 0, "c": 3}, how can you print only keys that exist and have a non-zero value?

hard

A. for k := range m { if m[k] { fmt.Println(k) } }

B. for k, v := range m { if v != 0 { fmt.Println(k) } }

C. for k, v := range m { if m[k] != nil { fmt.Println(k) } }

D. for k, v := range m { if v { fmt.Println(k) } }

Solution

1. Step 1: Iterate over map with key and value

   Use for k, v := range m to get keys and values.

2. Step 2: Check for non-zero values

   Check if v != 0 to filter keys with non-zero values.

3. Step 3: Print keys that meet condition

   Print the key k inside the if block.

4. Final Answer:

   for k, v := range m { if v != 0 { fmt.Println(k) } } -> Option B

5. Quick Check:

   Filter keys by value != 0 using range loop [OK]

Hint: Use for k,v := range map and check v != 0 [OK]

Common Mistakes:

• Using value as boolean directly
• Checking map key against nil
• Ignoring zero values in condition