Boolean indexing for filtering in NumPy - Time & Space Complexity

Time Complexity: Boolean indexing for filtering

O(n)

Understanding Time Complexity

We want to understand how the time needed to filter data with boolean indexing changes as the data size grows.

How does the filtering step scale when we have more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.arange(1000)
mask = arr % 2 == 0
filtered = arr[mask]

This code creates an array of numbers, makes a mask for even numbers, and filters the array using that mask.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element to create the boolean mask and then selecting elements based on that mask.
• How many times: Once for each element in the array (n times).

How Execution Grows With Input

As the array size grows, the number of checks and selections grows proportionally.

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

Pattern observation: The work grows directly with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter grows in a straight line as the data size increases.

Common Mistake

[X] Wrong: "Filtering with boolean indexing is instant no matter how big the array is."

[OK] Correct: The code must check each element to decide if it matches the condition, so more data means more work.

Interview Connect

Understanding how filtering scales helps you explain data processing steps clearly and shows you know how to handle bigger datasets efficiently.

Self-Check

"What if we used multiple conditions combined with & or | in the mask? How would the time complexity change?"

Practice

1. What does boolean indexing in numpy allow you to do?

easy

A. Select elements from an array based on True/False conditions

B. Sort an array in ascending order

C. Change the data type of an array

D. Calculate the sum of all elements in an array

Solution

1. Step 1: Understand boolean indexing concept

   Boolean indexing uses a True/False array to pick elements from another array.

2. Step 2: Compare with other options

   Sorting, changing data type, and summing are different numpy operations, not boolean indexing.

3. Final Answer:

   Select elements from an array based on True/False conditions -> Option A

4. Quick Check:

   Boolean indexing = filtering by True/False [OK]

Hint: Boolean indexing picks elements where condition is True [OK]

Common Mistakes:

• Confusing boolean indexing with sorting
• Thinking it changes data types
• Assuming it calculates sums

2. Which of the following is the correct syntax to filter array arr for values greater than 5 using boolean indexing?

easy

A. arr > 5[arr]

B. arr[arr > 5]

C. arr.filter(arr > 5)

D. arr[arr < 5]

Solution

1. Step 1: Identify correct boolean indexing syntax

   In numpy, filtering uses arr[condition] where condition is a boolean array.

2. Step 2: Check each option

   arr[arr > 5] uses correct syntax. arr > 5[arr] is invalid syntax. arr.filter(arr > 5) is not a numpy method. arr[arr < 5] filters for less than 5, not greater.

3. Final Answer:

   arr[arr > 5] -> Option B

4. Quick Check:

   Correct syntax is arr[condition] [OK]

Hint: Use arr[condition] to filter arrays in numpy [OK]

Common Mistakes:

• Placing condition outside brackets
• Using non-existent filter method
• Mixing up greater than and less than

3. What is the output of the following code?

import numpy as np
arr = np.array([2, 7, 4, 9, 1])
filtered = arr[arr % 2 == 1]

medium

A. [7 4 9]

B. [2 4]

C. [7 9 1]

D. [2 7 4 9 1]

Solution

1. Step 1: Understand the condition arr % 2 == 1

   This condition selects odd numbers because odd numbers have remainder 1 when divided by 2.

2. Step 2: Apply condition to array elements

   Elements 7, 9, and 1 are odd, so they are selected.

3. Final Answer:

   [7 9 1] -> Option C

4. Quick Check:

   Filter odd numbers = [7 9 1] [OK]

Hint: Use modulo (%) to filter odd/even numbers [OK]

Common Mistakes:

• Selecting even numbers instead of odd
• Including all elements without filtering
• Misunderstanding modulo operator

4. The following code throws an error. What is the mistake?

import numpy as np
arr = np.array([10, 15, 20, 25])
filtered = arr[arr > 15 and arr < 25]

medium

A. Using 'and' instead of '&' for element-wise condition

B. Missing parentheses around conditions

C. Using 'or' instead of 'and'

D. Array is not defined properly

Solution

1. Step 1: Identify boolean operator error

   In numpy, element-wise logical operations require '&' instead of Python's 'and'.

2. Step 2: Understand why 'and' causes error

   'and' expects single boolean, but arr > 15 and arr < 25 returns arrays, causing TypeError.

3. Final Answer:

   Using 'and' instead of '&' for element-wise condition -> Option A

4. Quick Check:

   Use '&' for element-wise logical AND [OK]

Hint: Use & with parentheses for multiple conditions [OK]

Common Mistakes:

• Using 'and' instead of '&' in numpy conditions
• Forgetting parentheses around each condition
• Assuming 'or' works like '|'

5. Given a numpy array data = np.array([3, 6, 9, 12, 15, 18]), how would you filter values that are divisible by 3 but not by 6 using boolean indexing?

hard

A. data[(data % 3 == 0) & (data % 6 == 0)]

B. data[(data % 3 == 0) | (data % 6 != 0)]

C. data[(data % 3 != 0) & (data % 6 == 0)]

D. data[(data % 3 == 0) & (data % 6 != 0)]

Solution

1. Step 1: Define conditions for filtering

   We want numbers divisible by 3 (data % 3 == 0) but not divisible by 6 (data % 6 != 0).

2. Step 2: Combine conditions with element-wise AND

   Use '&' to combine both conditions inside parentheses for correct boolean indexing.

3. Step 3: Apply combined condition to data array

   data[(data % 3 == 0) & (data % 6 != 0)] correctly applies both conditions with '&'. Others use wrong operators or conditions.

4. Final Answer:

   data[(data % 3 == 0) & (data % 6 != 0)] -> Option D

5. Quick Check:

   Use & and parentheses for combined conditions [OK]

Hint: Combine conditions with & and parentheses for filtering [OK]

Common Mistakes:

• Using | instead of & for AND condition
• Mixing up divisibility conditions
• Forgetting parentheses around each condition