Bird
Raised Fist0
Pythonprogramming~5 mins

Dictionary comprehension with condition in Python - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Time Complexity: Dictionary comprehension with condition
O(n)
Understanding Time Complexity

We want to understand how the time needed to build a dictionary using comprehension with a condition changes as the input grows.

Specifically, how does filtering items while creating a dictionary affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = range(1, n+1)
filtered_dict = {x: x*x for x in numbers if x % 2 == 0}

This code creates a dictionary of squares for even numbers from 1 to n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: Looping through each number from 1 to n.
  • How many times: Exactly n times, once for each number.
How Execution Grows With Input

As n grows, the code checks each number once and sometimes adds it to the dictionary.

Input Size (n)Approx. Operations
10About 10 checks and up to 5 insertions
100About 100 checks and up to 50 insertions
1000About 1000 checks and up to 500 insertions

Pattern observation: The number of checks grows directly with n, but insertions happen only for half the numbers (even ones).

Final Time Complexity

Time Complexity: O(n)

This means the time to build the dictionary grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "Because we only add half the items, the time is O(n/2), which is faster than O(n)."

[OK] Correct: Even though fewer items are added, the code still checks every number once, so the overall time still grows linearly with n.

Interview Connect

Understanding how filtering affects time helps you explain your code clearly and shows you can think about efficiency in everyday tasks.

Self-Check

"What if we changed the condition to check for prime numbers instead of even numbers? How would the time complexity change?"

Practice

(1/5)
1.

What does the following dictionary comprehension do?
{k: v for k, v in {'a': 1, 'b': 2, 'c': 3}.items() if v > 1}

easy
A. {'a': 1, 'b': 2, 'c': 3} - keeps all items
B. {'a': 1} - keeps items with values equal to 1
C. {'b': 2, 'c': 3} - keeps items with values greater than 1
D. {} - removes all items

Solution

  1. Step 1: Understand the dictionary comprehension structure

    The comprehension loops over each key-value pair in the original dictionary.

  2. Step 2: Apply the condition if v > 1

    Only pairs where the value is greater than 1 are included in the new dictionary.

  3. Final Answer:

    {'b': 2, 'c': 3} - keeps items with values greater than 1 -> Option C

  4. Quick Check:

    Filter values > 1 = {'b': 2, 'c': 3} [OK]
Hint: Look for the condition after the for loop to filter items [OK]
Common Mistakes:
  • Ignoring the condition and including all items
  • Confusing keys and values in the condition
  • Using wrong comparison operator
2.

Which of the following is the correct syntax for a dictionary comprehension with a condition?

?
easy
A. {k: v for k, v in d.items() if v % 2 == 0}
B. {k: v if v % 2 == 0 for k, v in d.items()}
C. {k: v for k, v in d.items() where v % 2 == 0}
D. {k: v for k, v in d.items() when v % 2 == 0}

Solution

  1. Step 1: Recall dictionary comprehension syntax

    The correct syntax is {key: value for key, value in iterable if condition}.

  2. Step 2: Identify the correct option

    {k: v for k, v in d.items() if v % 2 == 0} matches the correct syntax with if after the loop. Others use invalid keywords or wrong order.

  3. Final Answer:

    {k: v for k, v in d.items() if v % 2 == 0} -> Option A

  4. Quick Check:

    Correct syntax uses 'if' after for loop [OK]
Hint: Remember: condition goes after the for clause in comprehension [OK]
Common Mistakes:
  • Placing 'if' before the for loop
  • Using 'where' or 'when' instead of 'if'
  • Incorrect order of clauses
3.

What is the output of this code?

nums = {'x': 10, 'y': 5, 'z': 0}
filtered = {k: v for k, v in nums.items() if v}
print(filtered)

medium
A. {'x': 10, 'y': 5}
B. {}
C. {'z': 0}
D. {'x': 10, 'y': 5, 'z': 0}

Solution

  1. Step 1: Understand the condition if v

    This condition filters out values that are 'falsy' in Python, like 0, None, or empty.

  2. Step 2: Apply the condition to each item

    Values 10 and 5 are truthy, so included; 0 is falsy, so excluded.

  3. Final Answer:

    {'x': 10, 'y': 5} -> Option A

  4. Quick Check:

    Falsy values excluded = {'x': 10, 'y': 5} [OK]
Hint: Falsy values like 0 are skipped when condition is just 'if v' [OK]
Common Mistakes:
  • Including zero as truthy
  • Confusing keys and values
  • Expecting all items to be included
4.

Find the error in this dictionary comprehension:

data = {'a': 1, 'b': 2, 'c': 3}
result = {k: v for k, v in data.items() if v > 1 else 0}
print(result)

medium
A. No error, outputs {'b': 2, 'c': 3}
B. SyntaxError due to incorrect use of else in comprehension
C. Outputs {'a': 0, 'b': 2, 'c': 3}
D. KeyError because of else clause

Solution

  1. Step 1: Check the use of else in comprehension condition

    Dictionary comprehensions cannot have an else clause directly after the if condition.

  2. Step 2: Identify correct syntax

    To use else, it must be inside a value expression with a ternary operator, not after if.

  3. Final Answer:

    SyntaxError due to incorrect use of else in comprehension -> Option B

  4. Quick Check:

    else must be inside value expression, not after if [OK]
Hint: Use ternary inside value, not else after if in comprehension [OK]
Common Mistakes:
  • Placing else after if in comprehension
  • Confusing ternary operator syntax
  • Expecting else to filter keys
5.

You have a dictionary of student scores:
scores = {'Alice': 85, 'Bob': 42, 'Charlie': 73, 'David': 58}
Use dictionary comprehension with a condition to create a new dictionary passed containing only students who scored 60 or more, but store their scores as 'Pass' instead of the number.
Which code correctly does this?

hard
A. {k: 'Pass' for k, v in scores.items() if v > 60}
B. {k: 'Pass' if v >= 60 else 'Fail' for k, v in scores.items()}
C. {k: v for k, v in scores.items() if v >= 60}
D. {k: 'Pass' for k, v in scores.items() if v >= 60}

Solution

  1. Step 1: Understand the requirement

    We want only students with scores 60 or more, and their values replaced by 'Pass'.

  2. Step 2: Check each option

    {k: 'Pass' for k, v in scores.items() if v >= 60} filters with if v >= 60 and sets value to 'Pass'. {k: 'Pass' if v >= 60 else 'Fail' for k, v in scores.items()} includes all students with ternary but no filtering. {k: v for k, v in scores.items() if v >= 60} keeps original scores. {k: 'Pass' for k, v in scores.items() if v > 60} excludes 60 exactly.

  3. Final Answer:

    {k: 'Pass' for k, v in scores.items() if v >= 60} -> Option D

  4. Quick Check:

    Filter and replace value with 'Pass' = {k: 'Pass' for k, v in scores.items() if v >= 60} [OK]
Hint: Filter with if, set value directly to 'Pass' in comprehension [OK]
Common Mistakes:
  • Using else without filtering
  • Not including scores equal to 60
  • Keeping original scores instead of 'Pass'