Filter and filterNot in Kotlin - Time & Space Complexity

Time Complexity: Filter and filterNot

O(n)

Understanding Time Complexity

When we use filter or filterNot in Kotlin, we want to keep or remove items from a list based on a rule.

We ask: How does the time to do this change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf(1, 2, 3, 4, 5, 6)
val evenNumbers = numbers.filter { it % 2 == 0 }
val oddNumbers = numbers.filterNot { it % 2 == 0 }
    

This code creates a list of numbers, then makes two new lists: one with even numbers and one with odd numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each item in the list once to see if it matches the condition.
• How many times: Once for each item in the list (one pass per filter/filterNot call).

How Execution Grows With Input

Each item in the list is checked once per filter call, so the work grows as the list grows.

Input Size (n)	Approx. Operations
10	About 10 checks per filter call
100	About 100 checks per filter call
1000	About 1000 checks per filter call

Pattern observation: The number of checks grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "filter and filterNot are instant no matter how big the list is."

[OK] Correct: Each item must be checked, so bigger lists take more time.

Interview Connect

Understanding how filtering scales helps you write clear and efficient code, a skill that shows you think about how programs work in real life.

Self-Check

"What if we combined filter and filterNot into one pass? How would the time complexity change?"

Practice

1. What does the filter function do in Kotlin collections?

easy

A. Sorts the collection in ascending order

B. Removes all items from the collection

C. Keeps items where the condition is false

D. Keeps items where the condition is true

Solution

1. Step 1: Understand the purpose of filter

   The filter function selects elements that satisfy a given condition (true).

2. Step 2: Compare with other options

   Options B and D describe different operations, and C describes filterNot, not filter.

3. Final Answer:

   Keeps items where the condition is true -> Option D

4. Quick Check:

   filter = keep true items [OK]

Hint: Remember: filter keeps true, filterNot keeps false [OK]

Common Mistakes:

• Confusing filter with filterNot
• Thinking filter removes all items
• Mixing filter with sorting functions

2. Which of the following is the correct syntax to filter even numbers from a list numbers in Kotlin?

easy

A. numbers.filter { it / 2 == 0 }

B. numbers.filterNot { it % 2 == 0 }

C. numbers.filter { it % 2 == 0 }

D. numbers.filter { it % 2 != 0 }

Solution

1. Step 1: Identify the condition for even numbers

   Even numbers satisfy it % 2 == 0.

2. Step 2: Choose correct filter syntax

   filter keeps items where condition is true, so numbers.filter { it % 2 == 0 } keeps even numbers.

3. Final Answer:

   numbers.filter { it % 2 == 0 } -> Option C

4. Quick Check:

   filter with even condition = numbers.filter { it % 2 == 0 } [OK]

Hint: Use filter with condition true to keep desired items [OK]

Common Mistakes:

• Using filterNot instead of filter
• Using division instead of modulo
• Confusing condition signs (== vs !=)

3. What is the output of this Kotlin code?

val nums = listOf(1, 2, 3, 4, 5)
val result = nums.filterNot { it > 3 }
println(result)

medium

A. [1, 2, 3]

B. [4, 5]

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

D. []

Solution

1. Step 1: Understand filterNot condition

   filterNot { it > 3 } keeps items where it > 3 is false, so items ≤ 3.

2. Step 2: Apply condition to list

   Numbers 1, 2, 3 are ≤ 3, so they are kept; 4 and 5 are removed.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   filterNot > 3 = keep ≤ 3 [OK]

Hint: filterNot keeps items where condition is false [OK]

Common Mistakes:

• Confusing filterNot with filter
• Including numbers greater than 3
• Expecting empty list output

4. Find the error in this Kotlin code that tries to filter out odd numbers:

val numbers = listOf(1, 2, 3, 4, 5)
val evens = numbers.filterNot { it % 2 == 0 }
println(evens)

medium

A. The list is empty after filtering

B. It incorrectly keeps odd numbers instead of even

C. filterNot cannot be used with modulo operator

D. Syntax error in lambda expression

Solution

1. Step 1: Analyze the filterNot condition

   filterNot { it % 2 == 0 } keeps items where it % 2 == 0 is false, so it keeps odd numbers.

2. Step 2: Check intended output

   The code tries to get even numbers but actually keeps odd numbers, so logic is reversed.

3. Final Answer:

   It incorrectly keeps odd numbers instead of even -> Option B

4. Quick Check:

   filterNot with even condition keeps odd [OK]

Hint: filterNot reverses condition; use filter to keep true items [OK]

Common Mistakes:

• Using filterNot instead of filter for positive condition
• Assuming filterNot removes items instead of keeping false
• Misreading modulo condition

5. Given a list val words = listOf("apple", "banana", "", "cherry", ""), which Kotlin expression returns a list of only the non-empty words using filter and filterNot correctly?

hard

A. words.filter { it.isNotEmpty() }

B. words.filterNot { it.isNotEmpty() }

C. words.filter { it.isEmpty() }

D. words.filterNot { it.length > 0 }

Solution

1. Step 1: Identify condition for non-empty strings

   Non-empty strings satisfy it.isNotEmpty().

2. Step 2: Choose correct filter usage

   filter keeps items where condition is true, so words.filter { it.isNotEmpty() } returns only non-empty words.

3. Final Answer:

   words.filter { it.isNotEmpty() } -> Option A

4. Quick Check:

   filter with isNotEmpty = keep non-empty [OK]

Hint: Use filter with positive condition to keep desired items [OK]

Common Mistakes:

• Using filterNot with isNotEmpty to keep empty strings
• Confusing isEmpty and isNotEmpty
• Expecting filterNot to remove empty strings