Iterating over maps in Go - Time & Space Complexity

Time Complexity: Iterating over maps

O(n)

Understanding Time Complexity

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

We ask: How does the number of steps grow when the map has more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func printMap(m map[string]int) {
    for key, value := range m {
        fmt.Println(key, value)
    }
}
    

This code goes through each item in the map and prints its key and value.

Identify Repeating Operations

• Primary operation: Looping over each key-value pair in the map.
• How many times: Once for every item in the map.

How Execution Grows With Input

As the map gets bigger, the number of print steps grows in the same way.

Input Size (n)	Approx. Operations
10	10 print steps
100	100 print steps
1000	1000 print steps

Pattern observation: The work grows directly with the number of items in the map.

Final Time Complexity

Time Complexity: O(n)

This means if the map doubles in size, the time to loop through it roughly doubles too.

Common Mistake

[X] Wrong: "Looping over a map is always constant time because maps are fast."

[OK] Correct: While accessing one item is fast, looping visits every item, so time grows with map size.

Interview Connect

Understanding how looping over maps scales helps you explain your code's speed clearly and confidently.

Self-Check

"What if we nested a loop inside this loop to compare every map item with every other? How would the time complexity change?"

Practice

1.

What does the range keyword do when used with a map in Go?

easy

A. It creates a copy of the map.

B. It sorts the map by keys before looping.

C. It only loops over the keys, ignoring values.

D. It allows you to loop over all key-value pairs in the map.

Solution

1. Step 1: Understand the purpose of range with maps

   The range keyword in Go is used to iterate over elements in data structures like arrays, slices, and maps.

2. Step 2: Identify what happens with maps

   When used with a map, range returns both the key and the value for each item in the map.

3. Final Answer:

   It allows you to loop over all key-value pairs in the map. -> Option D

4. Quick Check:

   range with map = loop keys and values [OK]

Hint: Remember: range gives key and value for maps [OK]

Common Mistakes:

• Thinking range sorts the map
• Assuming range only returns keys
• Believing range copies the map

2.

Which of the following is the correct syntax to iterate over a map m in Go?

?

easy

A. for key, value := range m { /* code */ }

B. for (key, value) in m { /* code */ }

C. foreach key, value in m { /* code */ }

D. for key, value from m { /* code */ }

Solution

1. Step 1: Recall Go's for-range syntax

   In Go, the correct way to loop over a map is using for key, value := range mapName.

2. Step 2: Compare options

   Only for key, value := range m { /* code */ } uses the correct Go syntax with := and range keyword.

3. Final Answer:

   for key, value := range m { /* code */ } -> Option A

4. Quick Check:

   Go map iteration syntax = for key, value := range map [OK]

Hint: Use := with range to get key and value [OK]

Common Mistakes:

• Using Python or JavaScript style loops
• Missing := in the loop
• Using wrong keywords like foreach or from

3.

What will be the output of the following Go code?

package main
import "fmt"
func main() {
    m := map[string]int{"a": 1, "b": 2}
    for k, v := range m {
        fmt.Println(k, v)
    }
}

medium

A. Either 'a 1\nb 2' or 'b 2\na 1' (order not fixed)

B. b 2\na 1

C. a 1\nb 2

D. Compilation error

Solution

1. Step 1: Understand map iteration order in Go

   Maps in Go do not guarantee order when iterating. The keys can appear in any order.

2. Step 2: Analyze the output possibilities

   The code prints each key and value pair. The output could be 'a 1' then 'b 2' or 'b 2' then 'a 1'.

3. Final Answer:

   Either 'a 1\nb 2' or 'b 2\na 1' (order not fixed) -> Option A

4. Quick Check:

   Map iteration order = unpredictable [OK]

Hint: Map order is random; output order varies [OK]

Common Mistakes:

• Assuming map iteration order is fixed
• Expecting sorted output
• Thinking code causes error

4.

Identify the error in this Go code snippet that tries to iterate over a map m:

for key, value = range m {
    fmt.Println(key, value)
}

medium

A. Using 'range' incorrectly; should be 'for each'.

B. Using '=' instead of ':=' in the for loop.

C. Missing parentheses around key and value.

D. Map 'm' is not declared.

Solution

1. Step 1: Check the for loop variable declaration

   In Go, variables declared in a for-range loop must use ':=' to declare new variables.

2. Step 2: Identify the incorrect operator

   The code uses '=' which is assignment, not declaration, causing a syntax error.

3. Final Answer:

   Using '=' instead of ':=' in the for loop. -> Option B

4. Quick Check:

   Use ':=' to declare loop variables [OK]

Hint: Use ':=' not '=' in for-range loops [OK]

Common Mistakes:

• Using '=' instead of ':='
• Adding parentheses around variables
• Confusing 'range' with other keywords

5.

Given a map m := map[string]int{"x": 0, "y": 2, "z": 0}, how can you create a new map containing only keys with non-zero values by iterating over m?

hard

A. Use range but skip keys with zero values by deleting them from original map.

B. Use for key := range m and copy all keys regardless of value.

C. Create a new map and add pairs where value != 0 inside a for-range loop.

D. Sort the map and then filter keys with zero values.

Solution

1. Step 1: Understand the goal

   We want a new map with only keys whose values are not zero.

2. Step 2: Use for-range to check each key-value pair

   Iterate over m with for k, v := range m, and add to new map only if v != 0.

3. Step 3: Avoid modifying original map

   Do not delete keys from original map during iteration; create a new map instead.

4. Final Answer:

   Create a new map and add pairs where value != 0 inside a for-range loop. -> Option C

5. Quick Check:

   Filter map by value using new map and for-range [OK]

Hint: Build new map, add only non-zero values in loop [OK]

Common Mistakes:

• Deleting keys from map while iterating
• Copying all keys without filtering
• Trying to sort a map (not supported)