Boolean Indexing

1. Background Knowledge

NumPy arrays are the foundation for efficient numerical computing in Python, enabling vectorized operations that process entire arrays without explicit loops. Boolean indexing is a powerful NumPy feature that uses boolean masks (arrays of True/False values) to select elements matching a condition, returning a new array with those elements.

Key prerequisites:

• NumPy array creation: np.array([1, 2, 3])
• Element-wise comparisons: arr > threshold creates a boolean mask of same shape
• Indexing syntax: arr[condition] filters elements where condition is True

Example:

import numpy as np
arr = np.array([1, 5, 3, 8, 2, 9, 4, 7])
mask = arr > 5 # array([False, False, False, True, False, True, False, True])
greater = arr[mask] # array([8, 9, 7])

Boolean indexing returns a copy (not a view), ensuring the original array remains unchanged.

2. Algorithm Approach

The solution uses three boolean masks applied to the input array:

1. Greater mask: arr > threshold
2. Less/equal mask: arr <= threshold (complement of greater)
3. Count: Use np.sum() on boolean mask (True = 1, False = 0)

Core technique: Vectorized boolean operations + dictionary construction.

Mathematical foundation: For array $$\mathbf{a}$\in \mathbb{R}^n$ and threshold $t$,

greater = {a_i | a_i > t, i ∈ [0,n)}
less_equal = {a_i | a_i ≤ t, i ∈ [0,n)}
count_greater = |{i | a_i > t}| = ∑_{i=0}^{n-1} 𝟙(a_i > t)

where $𝟙$ is the indicator function.

3. Step-by-Step Strategy

def filter_array(arr, threshold):
 # Step 1: Create boolean masks (O(n) each)
 greater_mask = arr > threshold
 less_equal_mask = arr <= threshold # or ~greater_mask

 # Step 2: Apply masks to filter elements (O(n))
 greater_elements = arr[greater_mask].tolist()
 less_equal_elements = arr[less_equal_mask].tolist()

 # Step 3: Count using boolean sum (O(n))
 count_greater = np.sum(greater_mask)

 # Step 4: Return exact dictionary format
 return {
 "greater": greater_elements,
 "less_equal": less_equal_elements,
 "count_greater": count_greater
 }

Verification with sample:

arr = np.array([1, 5, 3, 8, 2, 9, 4, 7])
result = filter_array(arr, 5)
# {'greater': [8, 9, 7], 'less_equal': [1, 5, 3, 2, 4], 'count_greater': 3}

4. Common Pitfalls

• Returning NumPy arrays instead of lists: Use .tolist() for dictionary values
• Using Python len() instead of np.sum(): np.sum(boolean_mask) is faster and more idiomatic
• Modifying original array: Boolean indexing returns copies, but avoid arr[condition] = value unless intended
• Integer vs float thresholds: Works with both, but ensure threshold type matches array dtype
• Empty arrays: Handles correctly (greater: [], count_greater: 0)
• Missing keys or wrong names: Must match exactly: "greater", "less_equal", "count_greater"

# Wrong ❌
return {"gt": arr[arr>threshold], "count": len(arr[arr>threshold])}

# Correct ✅
return {"greater": arr[arr>threshold].tolist(), "count_greater": np.sum(arr>threshold)}

5. Time & Space Complexity

Time Complexity: $O(n)$ where $n = |$\mathbf{arr}$|$

• 3 boolean mask creations: $O(n)$ each
• 2 indexing operations: $O(n)$ total
• np.sum(): $O(n)$
• .tolist(): $O(k)$ where $k \leq n$

Space Complexity: $O(n)$

• Boolean masks: $O(n)$ each
• Output lists: $O(n)$ total
• Dictionary overhead: $O(1)$

Why optimal? Must read entire array to classify all elements; cannot short-circuit like scalar searches.

This vectorized NumPy approach is 100-1000x faster than equivalent Python loops due to C-level optimization and SIMD instructions.