Outlier detection with IQR in Pandas - Time & Space Complexity

Time Complexity: Outlier detection with IQR

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to find outliers using IQR changes as the data grows.

How does the work increase when we have more data points?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

# Assume df is a DataFrame with a numeric column 'values'
Q1 = df['values'].quantile(0.25)
Q3 = df['values'].quantile(0.75)
IQR = Q3 - Q1
outliers = df[(df['values'] < (Q1 - 1.5 * IQR)) | (df['values'] > (Q3 + 1.5 * IQR))]

This code calculates the IQR and finds rows where values are outliers based on that range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Pandas quantile internally sorts the 'values' column (O(n log n)) to compute order statistics, plus O(n) filtering.
• How many times: Two quantile calls (each O(n log n)) and one filtering pass (O(n)); dominated by sorting.

How Execution Grows With Input

As the number of data points grows, the time grows as O(n log n) due to sorting in quantiles.

Input Size (n)	Approx. Operations
10	About 70 (2 sorts ~60 + 10 filter)
100	About 1,400
1000	About 21,000

Pattern observation: Doubling n more than doubles the work due to the log n factor.

Final Time Complexity

Time Complexity: O(n log n)

Dominated by sorting within pandas quantile calls.

Common Mistake

[X] Wrong: "It's O(n) because we just scan the data a few times."

[OK] Correct: quantile requires sorting to find precise percentiles, costing O(n log n).

Interview Connect

Understanding how data size affects outlier detection helps you explain your approach clearly and shows you think about efficiency in real data tasks.

Self-Check

"Pandas quantile uses sorting (O(n log n)). What if we used a linear-time selection algorithm (like quickselect) for exact quantiles? How would complexity change?"

Practice

1. What does the Interquartile Range (IQR) represent in a dataset?

easy

A. The range between the 25th percentile (Q1) and the 75th percentile (Q3)

B. The difference between the maximum and minimum values

C. The average value of the dataset

D. The total number of data points

Solution

1. Step 1: Understand quartiles

   Quartiles divide data into four equal parts. Q1 is the 25th percentile, Q3 is the 75th percentile.

2. Step 2: Define IQR

   IQR is the difference between Q3 and Q1, showing the middle 50% spread of data.

3. Final Answer:

   The range between the 25th percentile (Q1) and the 75th percentile (Q3) -> Option A

4. Quick Check:

   IQR = Q3 - Q1 [OK]

Hint: IQR = Q3 minus Q1, middle half range [OK]

Common Mistakes:

• Confusing IQR with total range
• Thinking IQR is the average
• Mixing up quartiles with percentiles

2. Which of the following pandas code snippets correctly calculates the IQR of a DataFrame column df['score']?

easy

A. iqr = df['score'].mean() - df['score'].median()

B. iqr = df['score'].max() - df['score'].min()

C. iqr = df['score'].quantile(0.75) - df['score'].quantile(0.25)

D. iqr = df['score'].std()

Solution

1. Step 1: Recall IQR formula

   IQR is Q3 minus Q1, where Q3 is 75th percentile and Q1 is 25th percentile.

2. Step 2: Check pandas quantile usage

   Using quantile(0.75) and quantile(0.25) correctly gets Q3 and Q1.

3. Final Answer:

   iqr = df['score'].quantile(0.75) - df['score'].quantile(0.25) -> Option C

4. Quick Check:

   Use quantile(0.75) - quantile(0.25) for IQR [OK]

Hint: Use quantile(0.75) minus quantile(0.25) for IQR [OK]

Common Mistakes:

• Using mean or median instead of quantiles
• Using max-min instead of IQR
• Using standard deviation instead of IQR

3. Given the following code, what will be the output of outliers?

import pandas as pd

data = {'values': [10, 12, 14, 15, 18, 100, 105]}
df = pd.DataFrame(data)
Q1 = df['values'].quantile(0.25)
Q3 = df['values'].quantile(0.75)
IQR = Q3 - Q1
lower_bound = Q1 - 1.5 * IQR
upper_bound = Q3 + 1.5 * IQR
outliers = df[(df['values'] < lower_bound) | (df['values'] > upper_bound)]
print(outliers)

medium

A. Rows with values 10 and 12

B. Rows with values 100 and 105

C. All rows because 1.5*IQR is too small

D. Empty DataFrame, no outliers detected

Solution

1. Step 1: Calculate Q1, Q3, and IQR

   Q1 = 12.0 (between 12 and 14), Q3 = 18.0 (between 18 and 100), IQR = 6.0.

2. Step 2: Calculate bounds and find outliers

   Lower bound = 12 - 1.5*6 = 3; Upper bound = 18 + 1.5*6 = 27. Values 100 and 105 are above upper bound, so they are outliers.

3. Final Answer:

   Rows with values 100 and 105 -> Option B

4. Quick Check:

   Outliers > Q3 + 1.5*IQR or < Q1 - 1.5*IQR: 100, 105 [OK]

Hint: Outliers lie beyond Q1-1.5*IQR or Q3+1.5*IQR [OK]

Common Mistakes:

• Miscomputing Q1 or Q3
• Using wrong inequality signs
• Ignoring both lower and upper bounds

4. Identify the error in this code snippet for detecting outliers using IQR:

Q1 = df['data'].quantile(0.25)
Q3 = df['data'].quantile(0.75)
IQR = Q3 - Q1
outliers = df[(df['data'] > Q3 + 1.5 * IQR) & (df['data'] < Q1 - 1.5 * IQR)]

medium

A. No error, code is correct

B. IQR calculation is incorrect

C. Quantile values are swapped

D. The condition uses '&' instead of '|' to combine bounds

Solution

1. Step 1: Understand outlier condition

   Outliers are values less than lower bound OR greater than upper bound, so conditions should be combined with OR (|).

2. Step 2: Check code condition

   The code uses AND (&), which means no value can be both greater than upper bound and less than lower bound simultaneously.

3. Final Answer:

   The condition uses '&' instead of '|' to combine bounds -> Option D

4. Quick Check:

   Use '|' for outlier condition, not '&' [OK]

Hint: Use OR (|) to combine outlier conditions, not AND (&) [OK]

Common Mistakes:

• Using AND instead of OR for outlier filtering
• Swapping Q1 and Q3 values
• Calculating IQR incorrectly

5. You have a DataFrame df with a column 'height'. You want to remove outliers using IQR but keep the original index. Which code correctly filters out outliers and keeps the index intact?

hard

A. Q1 = df['height'].quantile(0.25)
Q3 = df['height'].quantile(0.75)
IQR = Q3 - Q1
filtered_df = df[(df['height'] >= Q1 - 1.5*IQR) & (df['height'] <= Q3 + 1.5*IQR)]

B. Q1 = df['height'].quantile(0.25)
Q3 = df['height'].quantile(0.75)
IQR = Q3 - Q1
filtered_df = df.reset_index(drop=True)[(df['height'] >= Q1 - 1.5*IQR) & (df['height'] <= Q3 + 1.5*IQR)]

C. Q1 = df['height'].quantile(0.25)
Q3 = df['height'].quantile(0.75)
IQR = Q3 - Q1
filtered_df = df[(df['height'] > Q1 + 1.5*IQR) | (df['height'] < Q3 - 1.5*IQR)]

D. Q1 = df['height'].quantile(0.25)
Q3 = df['height'].quantile(0.75)
IQR = Q3 - Q1
filtered_df = df[(df['height'] < Q1 - 1.5*IQR) & (df['height'] > Q3 + 1.5*IQR)]

Solution

1. Step 1: Calculate IQR and bounds correctly

   Calculate Q1, Q3, and IQR. Define lower bound as Q1 - 1.5*IQR and upper bound as Q3 + 1.5*IQR.

2. Step 2: Filter rows within bounds and keep index

   Use boolean indexing with AND (&) to keep rows inside bounds. Do not reset index to keep original indices.

3. Final Answer:

   Code in option A correctly filters and keeps index -> Option A

4. Quick Check:

   Filter with AND inside bounds, no reset_index [OK]

Hint: Filter with AND inside bounds; avoid resetting index [OK]

Common Mistakes:

• Using OR instead of AND to filter
• Resetting index and losing original row labels
• Swapping bounds or using wrong inequalities