Interpolation for missing values in Pandas - Time & Space Complexity

Time Complexity: Interpolation for missing values

O(n)

Understanding Time Complexity

We want to understand how the time needed to fill missing data by interpolation changes as the data size grows.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd
import numpy as np

# Create a DataFrame with missing values
n = 1000
values = np.random.rand(n)
values[::10] = np.nan  # Insert NaNs every 10 steps

df = pd.DataFrame({'A': values})

# Interpolate missing values
result = df['A'].interpolate(method='linear')

This code creates a column with missing values and fills them by linear interpolation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the column to find missing values and calculating interpolated values between known points.
• How many times: The operation runs roughly once over the entire data length, processing each element to fill gaps.

How Execution Grows With Input

As the number of data points grows, the time to interpolate grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 steps to check and fill missing values
100	About 100 steps
1000	About 1000 steps

Pattern observation: Doubling the data roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to interpolate grows linearly with the number of data points.

Common Mistake

[X] Wrong: "Interpolation time grows faster than the data size because it does complex calculations for each missing value."

[OK] Correct: Linear interpolation only looks at neighbors and fills gaps in one pass, so the work grows steadily, not faster.

Interview Connect

Understanding how interpolation scales helps you explain data cleaning steps clearly and shows you can think about efficiency in real data tasks.

Self-Check

"What if we changed the interpolation method to polynomial of degree 3? How would the time complexity change?"

Practice

1. What does the interpolate() method in pandas do when applied to a DataFrame with missing values?

easy

A. It fills missing values by estimating them based on nearby known values.

B. It deletes all rows containing missing values.

C. It replaces missing values with zeros.

D. It converts missing values to strings.

Solution

1. Step 1: Understand the purpose of interpolation

   Interpolation estimates missing data points by using values around them to create a smooth transition.

2. Step 2: Recognize what pandas interpolate() does

   The method fills missing values by calculating estimates based on existing nearby values, not by deleting or replacing with fixed values.

3. Final Answer:

   It fills missing values by estimating them based on nearby known values. -> Option A

4. Quick Check:

   Interpolation = estimate missing values [OK]

Hint: Interpolation estimates missing data using nearby values [OK]

Common Mistakes:

• Thinking it deletes rows with missing data
• Assuming it fills with zeros automatically
• Confusing interpolation with data type conversion

2. Which of the following is the correct syntax to interpolate missing values in a pandas DataFrame named df using the default method?

easy

A. df.interpolate(method='fill')

B. df.interpolate()

C. df.fillna(method='interpolate')

D. df.fillna(interpolate=True)

Solution

1. Step 1: Recall pandas interpolation syntax

   The method to fill missing values by interpolation is called directly as interpolate() on the DataFrame.

2. Step 2: Check each option for correctness

   df.interpolate() uses df.interpolate() which is correct. Options A, B, and D misuse fillna() or wrong parameters.

3. Final Answer:

   df.interpolate() -> Option B

4. Quick Check:

   Correct method call = df.interpolate() [OK]

Hint: Use df.interpolate() to fill missing values by default [OK]

Common Mistakes:

• Using fillna with wrong parameters
• Confusing interpolate with fillna method
• Adding invalid arguments to interpolate

3. Given the DataFrame df below, what will be the output of df.interpolate()?

import pandas as pd
import numpy as np
df = pd.DataFrame({'A': [1, np.nan, np.nan, 4, 5]})
print(df.interpolate())

medium

A. A
0 1.0
1 NaN
2 NaN
3 4.0
4 5.0

B. A
0 1.0
1 1.0
2 1.0
3 4.0
4 5.0

C. A
0 1.0
1 2.0
2 3.0
3 4.0
4 5.0

D. A
0 1.0
1 2.5
2 3.5
3 4.0
4 5.0

Solution

1. Step 1: Understand linear interpolation on missing values

   Linear interpolation fills missing values by evenly spacing values between known points. Here, missing values between 1 and 4 are filled as 2.0 and 3.0.

2. Step 2: Apply interpolation to the DataFrame

   Positions 1 and 2 are NaN. Interpolated values are 2.0 and 3.0 respectively, resulting in the sequence 1.0, 2.0, 3.0, 4.0, 5.0.

3. Final Answer:

   A 0 1.0 1 2.0 2 3.0 3 4.0 4 5.0 -> Option C

4. Quick Check:

   Linear interpolation fills gaps evenly [OK]

Hint: Linear interpolate fills gaps evenly between known values [OK]

Common Mistakes:

• Assuming missing values remain NaN
• Filling missing with previous value only
• Using wrong interpolation method

4. You run the code below but get an error. What is the most likely cause?

import pandas as pd
df = pd.DataFrame({'date': ['2023-01-01', '2023-01-02', '2023-01-03'], 'value': [1, None, 3]})
df['date'] = pd.to_datetime(df['date'])
df.interpolate(method='time')

medium

A. The DataFrame index is not set to the datetime column.

B. The 'value' column contains None instead of np.nan.

C. The 'date' column is not converted to datetime.

D. The interpolate method 'time' is not supported.

Solution

1. Step 1: Understand 'time' interpolation requirement

   The 'time' method requires the DataFrame index to be a datetime type to interpolate based on time differences.

2. Step 2: Check DataFrame index and columns

   Here, 'date' is a column but not set as index. Without datetime index, 'time' interpolation raises an error.

3. Final Answer:

   The DataFrame index is not set to the datetime column. -> Option A

4. Quick Check:

   Time interpolation needs datetime index [OK]

Hint: Set datetime column as index before time interpolation [OK]

Common Mistakes:

• Not setting datetime column as index
• Confusing None with np.nan (both work here)
• Assuming 'time' method unsupported

5. You have a DataFrame df with missing values in multiple columns and a datetime index. You want to fill missing values using time-based interpolation only on column 'temperature' without affecting others. Which code snippet correctly does this?

hard

A. df['temperature'].fillna(method='time')

B. df.interpolate(method='time', columns=['temperature'])

C. df.interpolate(method='time').loc[:, 'temperature']

D. df['temperature'] = df['temperature'].interpolate(method='time')

Solution

1. Step 1: Understand column-specific interpolation

   To interpolate only one column, call interpolate() on that column's Series.

2. Step 2: Check each option's correctness

   df['temperature'] = df['temperature'].interpolate(method='time') applies interpolation with method='time' directly on 'temperature' column and assigns back, which is correct. df.interpolate(method='time', columns=['temperature']) uses invalid 'columns' parameter. df.interpolate(method='time').loc[:, 'temperature'] interpolates whole DataFrame then selects column but does not assign back. df['temperature'].fillna(method='time') uses invalid fillna method.

3. Final Answer:

   df['temperature'] = df['temperature'].interpolate(method='time') -> Option D

4. Quick Check:

   Interpolate single column by calling method on that column [OK]

Hint: Interpolate single column by calling interpolate() on it [OK]

Common Mistakes:

• Using invalid 'columns' parameter in interpolate
• Not assigning interpolated result back to column
• Using fillna with method='time' which is invalid