Counting with boolean arrays in NumPy - Time & Space Complexity

Time Complexity: Counting with boolean arrays

O(n)

Understanding Time Complexity

We want to understand how the time to count True values in a boolean array changes as the array grows.

How does the work needed grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.random.choice([True, False], size=1000)
count_true = np.sum(arr)
print(count_true)

This code creates a boolean array and counts how many values are True.

Identify Repeating Operations

• Primary operation: Summing all elements in the boolean array.
• How many times: Once over all elements, so the number of elements times.

How Execution Grows With Input

Counting True values means checking each element once.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to count True values grows linearly as the array size grows.

Common Mistake

[X] Wrong: "Counting True values is instant regardless of array size."

[OK] Correct: The program must look at each element at least once to know if it is True or False, so time grows with array size.

Interview Connect

Understanding how counting works helps you explain efficiency clearly and shows you know how data size affects performance.

Self-Check

"What if we used a sparse representation for the boolean array? How would the time complexity change?"

Practice

1. What does summing a boolean array in NumPy do?
arr = np.array([True, False, True])
What is arr.sum()?

easy

A. Returns the length of the array

B. Counts how many False values are in the array

C. Counts how many True values are in the array

D. Returns an error because booleans cannot be summed

Solution

1. Step 1: Understand boolean values in NumPy

   In NumPy, True is treated as 1 and False as 0 when summed.

2. Step 2: Sum the boolean array

   Summing [True, False, True] is 1 + 0 + 1 = 2.

3. Final Answer:

   Counts how many True values are in the array -> Option C

4. Quick Check:

   True count = 2 [OK]

Hint: Sum boolean arrays to count True values quickly [OK]

Common Mistakes:

• Thinking sum counts False values
• Believing sum returns array length
• Expecting an error when summing booleans

2. Which of the following is the correct syntax to count how many elements in arr = np.array([1, 2, 3, 4]) are greater than 2 using boolean arrays?

easy

A. (arr > 2).sum()

B. arr > 2.sum()

C. arr.sum() > 2

D. arr > 2).sum()

Solution

1. Step 1: Create boolean array for condition

   arr > 2 creates a boolean array: [False, False, True, True].

2. Step 2: Sum the boolean array correctly

   We must sum the boolean array, so use parentheses: (arr > 2).sum().

3. Final Answer:

   (arr > 2).sum() -> Option A

4. Quick Check:

   Correct syntax uses parentheses [OK]

Hint: Use parentheses around condition before sum() [OK]

Common Mistakes:

• Missing parentheses causing wrong order
• Using sum() on condition without parentheses
• Confusing comparison and sum order

3. What is the output of this code?

import numpy as np
arr = np.array([5, 3, 8, 1, 6])
count = (arr % 2 == 0).sum()
print(count)

medium

A. 3

B. 0

C. 5

D. 2

Solution

1. Step 1: Create boolean array for even numbers

   arr % 2 == 0 checks which elements are even: [False, False, True, False, True].

2. Step 2: Sum True values to count evens

   Sum is 0 + 0 + 1 + 0 + 1 = 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Count of even numbers = 2 [OK]

Hint: Sum boolean condition to count matching elements [OK]

Common Mistakes:

• Counting odd numbers instead
• Forgetting to use parentheses
• Misunderstanding modulo operator

4. The code below is intended to count how many values in arr are less than 10, but it raises an error. What is the error and how to fix it?

import numpy as np
arr = np.array([7, 12, 5, 20])
count = arr < 10.sum()
print(count)

medium

A. Error: Missing import statement

B. Error: 10.sum() is invalid; fix by using (arr < 10).sum()

C. No error; output is boolean array

D. Error: arr < 10 is invalid; fix by using arr.sum() < 10

Solution

1. Step 1: Identify the error in expression

   10.sum() is invalid because 10 is an integer, not an array.

2. Step 2: Correct the syntax to sum boolean array

   Use parentheses to sum the boolean array: (arr < 10).sum().

3. Final Answer:

   Error: 10.sum() is invalid; fix by using (arr < 10).sum() -> Option B

4. Quick Check:

   Parentheses needed before sum() [OK]

Hint: Always put parentheses around condition before sum() [OK]

Common Mistakes:

• Calling sum() on number instead of boolean array
• Confusing comparison and sum order
• Ignoring error message details

5. Given a 2D NumPy array data = np.array([[3, 7, 2], [5, 1, 8], [6, 4, 9]]), how can you count how many elements are greater than 5 across the entire array?

hard

A. (data > 5).sum()

B. data[data > 5].count()

C. data.sum() > 5

D. np.count(data > 5)

Solution

1. Step 1: Create boolean array for elements > 5

   data > 5 creates a boolean array marking elements greater than 5.

2. Step 2: Sum True values to count elements

   Use (data > 5).sum() to count all True values in the 2D array.

3. Final Answer:

   (data > 5).sum() -> Option A

4. Quick Check:

   Sum boolean mask counts elements > 5 [OK]

Hint: Sum boolean mask over entire array to count matches [OK]

Common Mistakes:

• Using sum() on data directly
• Trying to use count() method on NumPy array
• Using non-existent np.count() function