Linear Interpolation
Linear Interpolation
Linear interpolation is a method for filling in missing values in a sequence by drawing a straight line between the nearest known values on each side. It is one of the most common imputation techniques for time series data, preserving the local trend between observed points.
Given a Python list of numbers where some entries are None (missing), fill in the missing values using linear interpolation between the nearest known neighbors. Return a new Python list (do not use NumPy).
Algorithm
For each gap of consecutive None values between known values at positions left and right:
value[j]=vleft+right−leftj−left⋅(vright−vleft)where j is the position of the missing value, and v_left, v_right are the known values bounding the gap.
Function Arguments
values: list— A Python list of numbers andNonevalues. The first and last elements are always numbers (neverNone).
Returns
list— A new Python list of the same length with allNonevalues replaced by their interpolated values.
Examples
Input:
values = [1, None, 3]
Output:
[1, 2.0, 3]
The missing value at index 1 is linearly interpolated between 1 (index 0) and 3 (index 2): 1 + (1/2) × (3 - 1) = 2.0.
Input:
values = [0, None, None, 6]
Output:
[0, 2.0, 4.0, 6]
Two missing values between 0 and 6. The gap spans 3 intervals: index 1 gets 0 + (1/3)×6 = 2.0, index 2 gets 0 + (2/3)×6 = 4.0.
Hint 1
Scan through the list. When you find a None, find the index of the last known value (left) and the next known value (right). Then fill each position j in between using the linear formula: left_val + (j - left) / (right - left) * (right_val - left_val).
Hint 2
Copy the input list. Use a while loop to scan for None values. When found, search forward for the next non-None. Compute the span (right - left) and interpolate each missing position proportionally.
Requirements
- Fill each None value using linear interpolation between the nearest known values on either side
- The first and last values are guaranteed to be non-None
- Preserve all non-None values unchanged
- Return a list with no None values remaining
Constraints
- values has at least 1 element
- First and last elements are not None
- Values are numbers or None
- Return a list of numbers with no None values
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Linear Interpolation
Linear Interpolation
Linear interpolation is a method for filling in missing values in a sequence by drawing a straight line between the nearest known values on each side. It is one of the most common imputation techniques for time series data, preserving the local trend between observed points.
Given a Python list of numbers where some entries are None (missing), fill in the missing values using linear interpolation between the nearest known neighbors. Return a new Python list (do not use NumPy).
Algorithm
For each gap of consecutive None values between known values at positions left and right:
value[j]=vleft+right−leftj−left⋅(vright−vleft)where j is the position of the missing value, and v_left, v_right are the known values bounding the gap.
Function Arguments
values: list— A Python list of numbers andNonevalues. The first and last elements are always numbers (neverNone).
Returns
list— A new Python list of the same length with allNonevalues replaced by their interpolated values.
Examples
Input:
values = [1, None, 3]
Output:
[1, 2.0, 3]
The missing value at index 1 is linearly interpolated between 1 (index 0) and 3 (index 2): 1 + (1/2) × (3 - 1) = 2.0.
Input:
values = [0, None, None, 6]
Output:
[0, 2.0, 4.0, 6]
Two missing values between 0 and 6. The gap spans 3 intervals: index 1 gets 0 + (1/3)×6 = 2.0, index 2 gets 0 + (2/3)×6 = 4.0.
Hint 1
Scan through the list. When you find a None, find the index of the last known value (left) and the next known value (right). Then fill each position j in between using the linear formula: left_val + (j - left) / (right - left) * (right_val - left_val).
Hint 2
Copy the input list. Use a while loop to scan for None values. When found, search forward for the next non-None. Compute the span (right - left) and interpolate each missing position proportionally.
Requirements
- Fill each None value using linear interpolation between the nearest known values on either side
- The first and last values are guaranteed to be non-None
- Preserve all non-None values unchanged
- Return a list with no None values remaining
Constraints
- values has at least 1 element
- First and last elements are not None
- Values are numbers or None
- Return a list of numbers with no None values
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array