Removing dictionary entries in Python - Time & Space Complexity

Time Complexity: Removing dictionary entries

O(n)

Understanding Time Complexity

When we remove entries from a dictionary, we want to know how the time it takes changes as the dictionary grows.

We ask: How does removing items scale with the number of entries?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_dict = {i: i*2 for i in range(n)}
for key in list(my_dict.keys()):
    if key % 2 == 0:
        del my_dict[key]

This code creates a dictionary with n entries and removes all entries with even keys.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over all keys in the dictionary.
• How many times: Exactly n times, once for each key.
• Secondary operation: Deleting entries from the dictionary inside the loop.

How Execution Grows With Input

As the dictionary size grows, the number of operations grows roughly the same way.

Input Size (n)	Approx. Operations
10	About 10 checks and some deletions
100	About 100 checks and deletions
1000	About 1000 checks and deletions

Pattern observation: The work grows directly with the number of entries; doubling entries roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Deleting items from a dictionary inside a loop is constant time and does not affect overall time."

[OK] Correct: Each deletion takes average constant time, and since deletions happen inside a loop over n items, the total time grows with n.

Interview Connect

Understanding how dictionary operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we removed items without converting keys to a list first? How would the time complexity change?"

Practice

1. What does the pop(key) method do when used on a Python dictionary?

easy

A. Removes the key and returns its value

B. Removes the key without returning its value

C. Returns the value without removing the key

D. Deletes the entire dictionary

Solution

1. Step 1: Understand the pop method

   The pop(key) method removes the specified key from the dictionary and returns its value.

2. Step 2: Compare with other methods

   Unlike del dict[key], pop returns the removed value.

3. Final Answer:

   Removes the key and returns its value -> Option A

4. Quick Check:

   pop(key) = remove key + return value [OK]

Hint: pop returns value and removes key from dict [OK]

Common Mistakes:

• Thinking pop only returns value without removal
• Confusing pop with del which doesn't return value
• Assuming pop deletes entire dictionary

2. Which of the following is the correct syntax to remove a key 'age' from dictionary person without returning its value?

easy

A. person.delete('age')

B. person.pop('age')

C. person.remove('age')

D. del person['age']

Solution

1. Step 1: Identify syntax for deletion without return

   To remove a key without returning its value, use del dict[key].

2. Step 2: Check options

   del person['age'] uses del person['age'], which is correct syntax. Options C and D are invalid methods.

3. Final Answer:

   del person['age'] -> Option D

4. Quick Check:

   del dict[key] removes key without return [OK]

Hint: Use del dict[key] to remove key without return [OK]

Common Mistakes:

• Using pop when no return is needed
• Using non-existent methods like remove or delete
• Wrong syntax like person.delete('age')

3. What is the output of this code?

data = {'a': 1, 'b': 2, 'c': 3}
value = data.pop('b')
print(value, data)

medium

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

B. None {'a': 1, 'c': 3}

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

D. KeyError

Solution

1. Step 1: Use pop to remove key 'b'

   The pop('b') removes key 'b' and returns its value 2.

2. Step 2: Print returned value and updated dictionary

   After removal, dictionary is {'a': 1, 'c': 3}. Printing value and dict shows: 2 {'a': 1, 'c': 3}.

3. Final Answer:

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

4. Quick Check:

   pop returns value and removes key [OK]

Hint: pop returns value and removes key from dict [OK]

Common Mistakes:

• Expecting original dict unchanged
• Thinking pop returns None
• Confusing pop with del which returns nothing

4. What error will this code produce?

info = {'name': 'Alice', 'age': 30}
info.pop('gender')

medium

A. None

B. KeyError

C. Returns 'gender'

D. SyntaxError

Solution

1. Step 1: Understand pop behavior without default

   Calling pop on a missing key without a default raises a KeyError.

2. Step 2: Check code

   Since 'gender' is not in info, info.pop('gender') raises KeyError.

3. Final Answer:

   KeyError -> Option B

4. Quick Check:

   pop missing key without default = KeyError [OK]

Hint: pop missing key without default causes KeyError [OK]

Common Mistakes:

• Expecting None instead of error
• Thinking pop returns the key name
• Confusing with pop(key, default)

5. Given items = {'apple': 5, 'banana': 0, 'cherry': 7}, which code removes all entries with value 0 or less safely without errors?

hard

A. for k in list(items):
if items[k] <= 0:
items.pop(k)

B. for k in items:
if items[k] <= 0:
del items[k]

C. items.pop('banana')

D. del items['banana']

Solution

1. Step 1: Avoid modifying dict while iterating

   Directly deleting keys while iterating causes runtime errors. Using list(items) copies keys safely.

2. Step 2: Use pop to remove keys with value ≤ 0

   Loop over copied keys, check value, and use pop to remove safely.

3. Final Answer:

   for k in list(items): if items[k] <= 0: items.pop(k) -> Option A

4. Quick Check:

   Iterate on list copy + pop keys safely [OK]

Hint: Iterate on list(items) to safely remove keys while looping [OK]

Common Mistakes:

• Deleting keys directly while iterating causes error
• Using pop without copying keys list
• Removing only one key instead of all matching