filter() function in Python - Time & Space Complexity

Time Complexity: filter() function

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run the filter() function changes as the input list gets bigger.

Specifically, how does the number of items affect the work done inside filter()?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
filtered = list(filter(lambda x: x % 2 == 0, numbers))
print(filtered)

This code filters out even numbers from a list of numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The filter() function checks each item in the list one by one.
• How many times: It runs the check exactly once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the number of checks grows in the same way.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows directly with the number of items. Double the items, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter grows in a straight line with the size of the list.

Common Mistake

[X] Wrong: "The filter function only checks some items, so it runs faster than looking at every item."

[OK] Correct: The filter function must look at every item to decide if it passes the test or not, so it always checks all items.

Interview Connect

Understanding how filter() works helps you explain how your code handles data efficiently, a useful skill in many coding discussions.

Self-Check

"What if the filtering function itself took longer to run for each item? How would that affect the overall time complexity?"

Practice

1. What does the filter() function do in Python?

easy

A. Sorts the items in a list

B. Changes all items in a list to uppercase

C. Selects items from a list that meet a condition

D. Adds all items in a list together

Solution

1. Step 1: Understand the purpose of filter()

   The filter() function takes a function and a list, then keeps only items where the function returns True.

2. Step 2: Compare options with the purpose

   Only Selects items from a list that meet a condition describes selecting items based on a condition, which matches filter()'s job.

3. Final Answer:

   Selects items from a list that meet a condition -> Option C

4. Quick Check:

   filter() selects items [OK]

Hint: Remember: filter keeps items passing the test [OK]

Common Mistakes:

• Thinking filter changes items instead of selecting
• Confusing filter with map or sort
• Assuming filter adds or combines items

2. Which of these is the correct syntax to use filter() to keep even numbers from a list nums?

easy

A. filter(lambda x: x % 2 == 0, nums)

B. filter(nums, lambda x: x % 2 == 0)

C. filter(x % 2 == 0, nums)

D. filter(lambda x: nums % 2 == 0)

Solution

1. Step 1: Recall filter() syntax

   The correct syntax is filter(function, iterable), where function tests each item.

2. Step 2: Check each option

   filter(lambda x: x % 2 == 0, nums) uses lambda x: x % 2 == 0 as function and nums as iterable, which is correct.

3. Final Answer:

   filter(lambda x: x % 2 == 0, nums) -> Option A

4. Quick Check:

   filter(function, iterable) correct order [OK]

Hint: filter(function, iterable) order matters [OK]

Common Mistakes:

• Swapping function and iterable arguments
• Using expression instead of function
• Missing lambda or function for filtering

3. What is the output of this code?

nums = [1, 2, 3, 4, 5]
even_nums = list(filter(lambda x: x % 2 == 0, nums))
print(even_nums)

medium

A. [1, 3, 5]

B. [2, 4]

C. [1, 2, 3, 4, 5]

D. []

Solution

1. Step 1: Understand the filter condition

   The lambda function keeps numbers where x % 2 == 0, meaning even numbers.

2. Step 2: Apply filter to the list

   From [1, 2, 3, 4, 5], only 2 and 4 are even, so the filtered list is [2, 4].

3. Final Answer:

   [2, 4] -> Option B

4. Quick Check:

   Filter keeps even numbers [OK]

Hint: Filter keeps items where function returns True [OK]

Common Mistakes:

• Confusing even and odd numbers
• Forgetting to convert filter to list
• Expecting original list unchanged

4. Find the error in this code snippet:

nums = [10, 15, 20]
result = filter(x % 10 == 0, nums)
print(list(result))

medium

A. Wrong variable name 'nums'

B. No error, code runs fine

C. filter() cannot be converted to list

D. Missing lambda function for filter

Solution

1. Step 1: Check filter function argument

   The first argument to filter() must be a function, but x % 10 == 0 is an expression, not a function.

2. Step 2: Identify fix

   We need to wrap the expression in a lambda: lambda x: x % 10 == 0 to make it a function.

3. Final Answer:

   Missing lambda function for filter -> Option D

4. Quick Check:

   filter needs a function as first argument [OK]

Hint: filter needs a function, use lambda for expressions [OK]

Common Mistakes:

• Passing expression instead of function
• Assuming filter returns list directly
• Ignoring syntax errors in lambda usage

5. You have a list of words: words = ['apple', '', 'banana', None, 'cherry', '']. Which code correctly filters out empty strings and None values using filter()?

hard

A. list(filter(lambda w: w, words))

B. list(filter(lambda w: w == '', words))

C. list(filter(lambda w: w is None, words))

D. list(filter(lambda w: w != None or w != '', words))

Solution

1. Step 1: Understand filtering out empty and None

   Empty strings and None are 'falsy' in Python, so lambda w: w keeps only truthy values.

2. Step 2: Check each option

   list(filter(lambda w: w, words)) keeps only truthy values, removing empty strings and None. Options B and C keep only empty or None, which is opposite. list(filter(lambda w: w != None or w != '', words)) uses wrong logic and keeps all.

3. Final Answer:

   list(filter(lambda w: w, words)) -> Option A

4. Quick Check:

   filter with lambda w: w removes falsy values [OK]

Hint: Use lambda x: x to remove falsy values [OK]

Common Mistakes:

• Using wrong condition to keep empty or None
• Using 'or' instead of 'and' in condition
• Expecting filter to remove without function