Inverting a dictionary in Python - Time & Space Complexity

Time Complexity: Inverting a dictionary

O(n)

Understanding Time Complexity

When we invert a dictionary, we swap its keys and values. Analyzing time complexity helps us see how the work grows as the dictionary gets bigger.

We want to know: how does the time to invert change when the dictionary has more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def invert_dict(d):
    inverted = {}
    for key, value in d.items():
        inverted[value] = key
    return inverted

This code creates a new dictionary where each original value becomes a key, and each original key becomes its value.

Identify Repeating Operations

• Primary operation: Looping through all key-value pairs in the dictionary.
• How many times: Once for each item in the dictionary.

How Execution Grows With Input

As the dictionary gets bigger, the number of steps grows directly with the number of items.

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

Pattern observation: The work grows evenly as the dictionary size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to invert the dictionary grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Inverting a dictionary takes the same time no matter how big it is."

[OK] Correct: The code must look at every item once, so more items mean more work.

Interview Connect

Understanding how loops affect time helps you explain your code clearly and shows you can think about efficiency, a key skill in programming.

Self-Check

"What if the dictionary values are not unique and we store lists of keys for each value? How would the time complexity change?"

Practice

1.

What does inverting a dictionary mean in Python?

easy

A. Sorting the dictionary by keys

B. Swapping keys and values so values become keys and keys become values

C. Removing duplicate keys from the dictionary

D. Changing all values to uppercase strings

Solution

1. Step 1: Understand dictionary structure

   A dictionary has keys and values paired together.

2. Step 2: Define inverting

   Inverting means swapping each key with its value, so keys become values and values become keys.

3. Final Answer:

   Swapping keys and values so values become keys and keys become values -> Option B

4. Quick Check:

   Inverting = swapping keys and values [OK]

Hint: Invert means swap keys and values in a dictionary [OK]

Common Mistakes:

• Thinking inverting sorts the dictionary
• Confusing inverting with removing duplicates
• Assuming values become uppercase strings

2.

Which of the following is the correct syntax to invert a dictionary d using dictionary comprehension?

easy

A. {k: v for k, v in d}

B. {k: v for v, k in d.items()}

C. {d[v]: d[k] for k, v in d.items()}

D. {v: k for k, v in d.items()}

Solution

1. Step 1: Recall dictionary comprehension syntax

   It uses {new_key: new_value for key, value in dict.items()}.

2. Step 2: Swap keys and values correctly

   To invert, new_key = value and new_value = key, so use {v: k for k, v in d.items()}.

3. Final Answer:

   {v: k for k, v in d.items()} -> Option D

4. Quick Check:

   Correct syntax = {v: k for k, v in d.items()} [OK]

Hint: Use {v: k for k, v in d.items()} to invert dictionary [OK]

Common Mistakes:

• Swapping variables incorrectly in comprehension
• Using d[v] or d[k] inside comprehension wrongly
• Forgetting to call .items() on dictionary

3.

What is the output of this code?

original = {'a': 1, 'b': 2, 'c': 3}
inverted = {v: k for k, v in original.items()}
print(inverted)

medium

A. {1: 'a', 2: 'b', 3: 'c'}

B. {'a': 1, 'b': 2, 'c': 3}

C. {'1': 'a', '2': 'b', '3': 'c'}

D. Error: unhashable type

Solution

1. Step 1: Understand original dictionary

   Keys are 'a', 'b', 'c' and values are 1, 2, 3.

2. Step 2: Invert dictionary using comprehension

   Swapping keys and values gives keys 1, 2, 3 and values 'a', 'b', 'c'.

3. Final Answer:

   {1: 'a', 2: 'b', 3: 'c'} -> Option A

4. Quick Check:

   Inverted dict = {1: 'a', 2: 'b', 3: 'c'} [OK]

Hint: Invert swaps keys and values exactly as pairs [OK]

Common Mistakes:

• Expecting original dictionary output
• Confusing string and integer keys
• Thinking inversion causes error here

4.

What is wrong with this code to invert a dictionary?

d = {'x': 10, 'y': 10}
inverted = {v: k for k, v in d.items()}
print(inverted)

medium

A. It will keep only one key for duplicate values

B. It will invert correctly with no issues

C. It will raise a TypeError

D. It will raise a KeyError

Solution

1. Step 1: Identify duplicate values in dictionary

   Both 'x' and 'y' have value 10, which is duplicated.

2. Step 2: Understand dictionary key uniqueness

   When inverting, keys must be unique, so only one key-value pair with key 10 remains.

3. Final Answer:

   It will keep only one key for duplicate values -> Option A

4. Quick Check:

   Duplicate values cause lost keys in inversion [OK]

Hint: Duplicate values become keys, only last key kept [OK]

Common Mistakes:

• Expecting all keys preserved after inversion
• Thinking it raises an error for duplicates
• Ignoring key uniqueness in dictionaries

5.

Given a dictionary with possible duplicate values, how can you invert it so each value maps to a list of keys that had that value?

original = {'a': 1, 'b': 2, 'c': 1}

Which code correctly inverts it to {1: ['a', 'c'], 2: ['b']}?

hard

A. inverted = {v: [k] for k, v in original.items()}

B. inverted = {v: k for k, v in original.items()}

C. inverted = {}
for k, v in original.items():
inverted.setdefault(v, []).append(k)

D. inverted = {v: k for v, k in original.items()}

Solution

1. Step 1: Understand problem with duplicates

   Simple inversion loses keys when values repeat, so we need lists to hold multiple keys.

2. Step 2: Use setdefault and append to collect keys

   Loop through items, for each value use setdefault to create list if missing, then append key.

3. Step 3: Check code correctness

   inverted = {} for k, v in original.items(): inverted.setdefault(v, []).append(k) uses this approach correctly, building lists of keys per value.

4. Final Answer:

   inverted = {} for k, v in original.items(): inverted.setdefault(v, []).append(k) -> Option C

5. Quick Check:

   Use setdefault + append to group keys by value [OK]

Hint: Use setdefault with append to group keys by value [OK]

Common Mistakes:

• Using simple comprehension losing duplicate keys
• Swapping variables incorrectly in comprehension
• Expecting one-to-one inversion with duplicates