Deleting map entries in Go - Time & Space Complexity

Time Complexity: Deleting map entries

O(1)

Understanding Time Complexity

When we delete entries from a map in Go, it is important to know how the time it takes changes as the map grows.

We want to understand how the cost of deleting one entry depends on the size of the map.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    m := map[int]string{1: "a", 2: "b", 3: "c"}
    delete(m, 2)
    

This code creates a map with three entries and deletes the entry with key 2.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Deleting a single key from the map.
• How many times: Once in this example, but could be repeated for multiple keys.

How Execution Grows With Input

Deleting one entry from a map takes about the same time no matter how many entries the map has.

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

Pattern observation: The time to delete does not grow with the map size; it stays roughly constant.

Final Time Complexity

Time Complexity: O(1)

This means deleting a key from a map takes about the same time no matter how big the map is.

Common Mistake

[X] Wrong: "Deleting a key takes longer if the map has more entries because it has to search through all keys."

[OK] Correct: Maps use a special way to find keys quickly, so deleting a key does not require checking every entry.

Interview Connect

Understanding that map deletions are fast helps you explain how data structures work efficiently in real programs.

Self-Check

"What if we delete multiple keys in a loop? How would the total time complexity change?"

Practice

1. What does the built-in delete function do in Go when used as delete(myMap, key)?

easy

A. Adds a new entry with the specified key to the map.

B. Returns the value associated with the key.

C. Clears all entries from the map.

D. Removes the entry with the specified key from the map if it exists.

Solution

1. Step 1: Understand the delete function purpose

   The delete function is used to remove a key and its value from a map.

2. Step 2: Analyze the effect of delete on the map

   When called as delete(myMap, key), it removes the entry if the key exists; otherwise, it does nothing.

3. Final Answer:

   Removes the entry with the specified key from the map if it exists. -> Option D

4. Quick Check:

   delete removes key from map [OK]

Hint: delete(map, key) removes key entry safely [OK]

Common Mistakes:

• Thinking delete adds or returns values
• Confusing delete with clearing the whole map
• Assuming delete returns a value

2. Which of the following is the correct syntax to delete a key named "user1" from a map called users in Go?

easy

A. delete(users, "user1")

B. users.delete("user1")

C. remove(users, "user1")

D. users.deleteKey("user1")

Solution

1. Step 1: Recall Go's delete syntax

   In Go, the built-in function delete is used as delete(map, key) to remove a key.

2. Step 2: Match the correct syntax

   delete(users, "user1") uses delete(users, "user1"), which is the correct syntax. Other options use methods that do not exist in Go.

3. Final Answer:

   delete(users, "user1") -> Option A

4. Quick Check:

   delete(map, key) syntax correct [OK]

Hint: Use delete(map, key) function, not method calls [OK]

Common Mistakes:

• Using method syntax like map.delete(key)
• Using non-existent functions like remove()
• Confusing with other languages' syntax

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

m := map[string]int{"a": 1, "b": 2}
delete(m, "a")
fmt.Println(m)

medium

A. map[a:1 b:2]

B. map[b:2]

C. map[]

D. Compilation error

Solution

1. Step 1: Understand initial map content

   The map m initially has two entries: "a":1 and "b":2.

2. Step 2: Effect of delete(m, "a")

   The delete call removes the key "a" and its value from the map, leaving only "b":2.

3. Final Answer:

   map[b:2] -> Option B

4. Quick Check:

   Deleting key "a" removes it from map [OK]

Hint: Deleting key removes it; print shows remaining entries [OK]

Common Mistakes:

• Expecting deleted key to remain
• Thinking delete clears whole map
• Assuming syntax error occurs

4. Consider this Go code snippet:

var m map[string]int
delete(m, "key")
fmt.Println("Done")

What will happen when this code runs?

medium

A. Compilation error because delete cannot be used on nil maps.

B. Runtime panic due to deleting from a nil map.

C. Prints "Done" without error.

D. Deletes the key if it exists, then prints "Done".

Solution

1. Step 1: Understand nil map behavior

   In Go, a nil map behaves like an empty map for reads and deletes; deleting a key from a nil map does nothing and does not panic.

2. Step 2: Analyze the code behavior

   Deleting from a nil map is safe and does not cause runtime panic. The program prints "Done" normally.

3. Final Answer:

   Prints "Done" without error. -> Option C

4. Quick Check:

   Deleting from nil map is safe [OK]

Hint: Deleting from nil map is safe, no panic occurs [OK]

Common Mistakes:

• Assuming runtime panic on deleting from nil map
• Thinking delete causes compilation error
• Confusing nil map with uninitialized map variable

5. You have a map m := map[string]int{"x": 10, "y": 0, "z": -5}. You want to delete all keys whose values are zero or less. Which code snippet correctly deletes these entries?

hard

A. for k, v := range m { if v <= 0 { delete(m, k) } }

B. for k := range m { if m[k] < 0 { delete(m, k) } }

C. for k, v := range m { if v == 0 { delete(m, k) } }

D. for k := range m { if m[k] == 0 { delete(m, k) } }

Solution

1. Step 1: Identify keys with values zero or less

   Keys with values <= 0 are "y" (0) and "z" (-5).

2. Step 2: Choose loop that deletes keys with v <= 0

   for k, v := range m { if v <= 0 { delete(m, k) } } uses for k, v := range m and deletes keys where v <= 0, correctly removing "y" and "z".

3. Step 3: Compare other options

   Options A and C check only for == 0, missing negative values like "z":-5. for k := range m { if m[k] < 0 { delete(m, k) } } checks m[k] < 0, missing zero values like "y":0.

4. Final Answer:

   for k, v := range m { if v <= 0 { delete(m, k) } } -> Option A

5. Quick Check:

   Delete keys with value <= 0 using k,v loop [OK]

Hint: Use for k,v range and delete if v <= 0 [OK]

Common Mistakes:

• Deleting only keys with value == 0, missing negatives
• Using only key without value in loop
• Modifying map incorrectly during iteration