1795. Rearrange Products Table
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 90.6%
Problem Breakdown
Restated Problem:
Given a table named Products with columns product_id, store1, store2, and store3, where each row represents the availability of a product in three different stores (with values indicating the quantity available), rearrange the data so that each row contains only one store’s information for a given product. The output should have columns product_id, store, and quantity.
Inputs:
- A table
Productswith columns:product_id: Unique identifier for each product.store1,store2,store3: Quantities of the product available in respective stores.
Outputs:
- A new table structure with columns:
product_id: Unique identifier for each product.store: Name of the store (either ‘store1’, ‘store2’, or ‘store3’).quantity: Quantity of the product available in that store.
Implicit Constraints/Edge Cases:
- The input table might be empty.
- There could be products with zero quantity in any store, which should still appear in the output.
- All
product_idvalues are unique.
Intuition
Brute-force Approach:
- Iterate through each row of the
Productstable. - For each product, check its availability in each store and create a new row for each non-zero quantity.
- This approach would involve multiple conditional checks and manual data insertion into a new table.
Why Brute-force is Insufficient:
- The brute-force method involves nested loops (one for rows and one for stores), leading to a time complexity of O(n * m), where n is the number of products and m is the number of stores. This can be inefficient for large datasets.
- It also requires manual handling of data insertion, which increases the risk of errors.
Key Insight:
Instead of manually checking each store’s quantity, we can use SQL’s UNION ALL to combine multiple SELECT statements that handle each store separately. This approach leverages SQL’s set operations to simplify the process and improve efficiency.
Approach
-
Identify the Data Structure:
- Use a combination of
SELECTstatements withUNION ALLto create a single result set that combines data from all stores.
- Use a combination of
-
Algorithm Steps:
- For each store (
store1,store2,store3), perform aSELECToperation to extract theproduct_idand quantity, while also adding a constant column indicating the store name. - Use
UNION ALLto combine the results of theseSELECTstatements into a single result set.
- For each store (
-
Why This Approach Works:
- Each
SELECTstatement handles one store’s data, reducing the complexity from O(n * m) to O(n + n + n), which simplifies to O(n). - The use of
UNION ALLensures that all rows are included in the final result set without any additional filtering or sorting.
- Each
Complexity Analysis
Time Complexity:
- O(n), where n is the number of products. Each product is processed once for each store, resulting in a linear time complexity relative to the number of products.
Space Complexity:
- O(n), as the space required is proportional to the number of rows in the final result set, which is equal to the number of products multiplied by the number of stores (3 in this case).
Solution
import pandas as pd
def rearrange_products_table(products: pd.DataFrame) -> pd.DataFrame:
# Select data for store1 and add a constant column 'store'
store1 = products[['product_id', 'store1']].rename(columns={'store1': 'quantity'}).assign(store='store1')
# Select data for store2 and add a constant column 'store'
store2 = products[['product_id', 'store2']].rename(columns={'store2': 'quantity'}).assign(store='store2')
# Select data for store3 and add a constant column 'store'
store3 = products[['product_id', 'store3']].rename(columns={'store3': 'quantity'}).assign(store='store3')
# Combine the results using UNION ALL
result = pd.concat([store1, store2, store3], ignore_index=True)
return result
Edge Cases Handled
- Empty Input Table: If the input table is empty, the
SELECToperations will also be empty, resulting in an empty output table. - Zero Quantity Products: Products with zero quantity in any store will still appear in the output with a quantity of 0.
- Unique Product IDs: The use of unique
product_idvalues ensures that each product is correctly identified and processed across all stores.