Fill Missing Data

Difficulty: Easy | Acceptance: 72.50% | Paid: No Topics: N/A

Table: Products

In SQL, name is the primary key for this table. This table contains the inventory of a store. quantity is the number of units sold. If quantity is null, it means the product has not been sold yet.

Write a solution to update the quantity for the missing values as the median of all the existing quantity values. The median is the middle value in a sorted list of numbers. If the list has an even number of elements, the median is the average of the two middle values. Round the median to the nearest integer. If the median is x.5, round it up to x + 1.

The result format is in the following example.

• Examples
• Constraints
• Pandas Built-in Methods
• Manual Iteration and Replacement

Examples

Example 1

Input:

+-----------------+----------+-------+
| name            | quantity | price |
+-----------------+----------+-------+
| Wristwatch      | None     | 135   |
| WirelessEarbuds | None     | 821   |
| GolfClubs       | 779      | 9319  |
| Printer         | 849      | 3051  |
+-----------------+----------+-------+

Output:

+-----------------+----------+-------+
| name            | quantity | price |
+-----------------+----------+-------+
| Wristwatch      | 0        | 135   |
| WirelessEarbuds | 0        | 821   |
| GolfClubs       | 779      | 9319  |
| Printer         | 849      | 3051  |
+-----------------+----------+-------+

Explanation: The quantity for Wristwatch and WirelessEarbuds are filled by 0.

Constraints

0 <= products.length <= 1000

Pandas Built-in Methods

Intuition Use the built-in Pandas functions to calculate the median and fill missing values efficiently without explicit loops.

Steps

• Calculate the median of the quantity column using the median() method.
• Round the median to the nearest integer, ensuring 0.5 rounds up.
• Use the fillna() method to replace all NaN values in the quantity column with the calculated median.

import pandas as pd
import numpy as np

def fillMissingData(products: pd.DataFrame) -> pd.DataFrame:
    # Calculate median of the quantity column, ignoring NaNs
    median_val = products['quantity'].median()
    
    # Round the median to the nearest integer (0.5 rounds up)
    # Python's round() uses bankers rounding, so we add 0.5 and floor
    rounded_median = int(median_val + 0.5)
    
    # Fill missing values with the rounded median
    products['quantity'] = products['quantity'].fillna(rounded_median)
    
    return products

Complexity

• Time: O(n log n) due to sorting.
• Space: O(n) to store valid quantities.
• Notes: Pandas implementation is highly optimized C under the hood, making it very fast for large datasets.

Manual Iteration and Replacement

Intuition Manually iterate through the data to collect valid values, sort them to find the median, and then iterate again to replace null values.

Steps

• Iterate through the list of products to collect all non-null quantity values.
• Sort the collected values.
• Calculate the median based on the sorted list (average of two middle elements if even length, middle element if odd).
• Round the median up if the decimal part is 0.5 or greater.
• Iterate through the original list again, replacing any null quantity with the calculated median.

import pandas as pd
import numpy as np

def fillMissingData(products: pd.DataFrame) -> pd.DataFrame:
    # Extract valid quantities manually
    valid_quantities = []
    for index, row in products.iterrows():
        if pd.notna(row['quantity']):
            valid_quantities.append(row['quantity'])
    
    # Sort manually
    valid_quantities.sort()
    
    # Calculate median
    n = len(valid_quantities)
    median = 0
    if n > 0:
        if n % 2 == 0:
            median = (valid_quantities[n//2 - 1] + valid_quantities[n//2]) / 2
        else:
            median = valid_quantities[n//2]
    
    # Round 0.5 up
    rounded_median = int(median + 0.5)
    
    # Replace NaNs manually
    for index, row in products.iterrows():
        if pd.isna(row['quantity']):
            products.at[index, 'quantity'] = rounded_median
            
    return products

Complexity

• Time: O(n log n) due to sorting the valid values.
• Space: O(n) to store the list of valid quantities.
• Notes: This approach demonstrates the underlying logic of data manipulation without relying on high-level library abstractions.