LeetCode 1795 - Rearrange Products Table
The Products table stores product prices across three different stores. Each row represents one product, identified by productid, and each store column contains the product's price in that specific store.
Difficulty: 🟢 Easy
Topics: Database
Solution
Problem Understanding
The Products table stores product prices across three different stores. Each row represents one product, identified by product_id, and each store column contains the product's price in that specific store.
The table has this structure:
| Column | Meaning |
|---|---|
product_id |
Unique identifier for the product |
store1 |
Price of the product in store1 |
store2 |
Price of the product in store2 |
store3 |
Price of the product in store3 |
The problem asks us to transform the table into a normalized format. Instead of storing all store prices in separate columns, we want each store-price pair to become its own row.
The final output must contain:
| Column | Meaning |
|---|---|
product_id |
Product identifier |
store |
Store name |
price |
Product price in that store |
One important requirement is that if a product is unavailable in a store, the corresponding column contains NULL, and we must not include that store in the result.
For example, if a row looks like this:
| product_id | store1 | store2 | store3 |
|---|---|---|---|
| 1 | 70 | NULL | 80 |
then the transformed output should only contain:
| product_id | store | price |
|---|---|---|
| 1 | store1 | 70 |
| 1 | store3 | 80 |
and not include store2.
This problem is essentially asking us to "unpivot" or "reshape" a wide table into a long table.
Since the table only contains three store columns, the input size is very manageable. The main challenge is correctly converting columns into rows while filtering out NULL values.
Important edge cases include products missing from all stores, products available in only one store, and rows where some store columns are NULL while others are valid prices. The problem guarantees that product_id is unique, so we never need to merge or deduplicate rows.
Approaches
Brute Force Approach
A straightforward approach is to manually inspect every store column for every product row.
For each row in the Products table:
- Check whether
store1is notNULL - If valid, output
(product_id, 'store1', store1) - Repeat the same process for
store2 - Repeat again for
store3
This works because every possible store-product combination is explicitly examined. If a price exists, we emit a corresponding row.
Although this approach is already efficient due to the small number of store columns, it becomes repetitive and less maintainable if the number of stores increases significantly.
Optimal Approach
The best SQL solution uses UNION ALL to combine multiple SELECT statements into a single normalized result set.
Each SELECT extracts rows for one store only:
- One query handles
store1 - One query handles
store2 - One query handles
store3
Each query filters out NULL values using WHERE storeX IS NOT NULL.
UNION ALL is preferred instead of UNION because we do not need duplicate removal, and avoiding duplicate elimination improves efficiency.
This approach is clean, readable, and directly models the transformation required by the problem.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Manually checks every store column |
| Optimal | O(n) | O(n) | Uses UNION ALL to reshape the table cleanly |
Algorithm Walkthrough
- Start with the
Productstable, where each row contains prices for up to three stores. - Create the first query for
store1.
Select:
product_id'store1'as the store namestore1as the price
Filter rows using:
WHERE store1 IS NOT NULL
This ensures unavailable products are excluded.
3. Create the second query for store2.
This query follows the exact same structure:
SELECT product_id, 'store2', store2
Again, filter out NULL values.
4. Create the third query for store3.
Repeat the same transformation logic.
5. Combine all three result sets using UNION ALL.
UNION ALL concatenates all rows together without attempting duplicate removal.
6. Return the combined result.
The final table now contains one row per (product_id, store) pair where a valid price exists.
Why it works
The algorithm works because every valid store column is independently transformed into rows. Each query extracts exactly the non-null entries for one store. Combining the queries with UNION ALL guarantees that every valid store-price pair appears exactly once in the final result.
Since NULL values are filtered before unioning the results, unavailable products are never included.
Python Solution
LeetCode Database problems are solved using SQL, but the platform still labels the language section. Below is the complete SQL solution.
SELECT product_id, 'store1' AS store, store1 AS price
FROM Products
WHERE store1 IS NOT NULL
UNION ALL
SELECT product_id, 'store2' AS store, store2 AS price
FROM Products
WHERE store2 IS NOT NULL
UNION ALL
SELECT product_id, 'store3' AS store, store3 AS price
FROM Products
WHERE store3 IS NOT NULL;
The query is divided into three logical sections, one for each store column.
The first query extracts all valid prices from store1. The literal string 'store1' is used to populate the store column in the result table.
The same logic is repeated for store2 and store3.
Each query filters out rows where the store price is NULL, ensuring unavailable products are excluded.
Finally, UNION ALL concatenates all generated rows into a single normalized result table.
Go Solution
SELECT product_id, 'store1' AS store, store1 AS price
FROM Products
WHERE store1 IS NOT NULL
UNION ALL
SELECT product_id, 'store2' AS store, store2 AS price
FROM Products
WHERE store2 IS NOT NULL
UNION ALL
SELECT product_id, 'store3' AS store, store3 AS price
FROM Products
WHERE store3 IS NOT NULL;
There are no Go-specific implementation details because LeetCode Database problems are solved entirely in SQL. The same SQL query is submitted regardless of the selected language.
Worked Examples
Example 1
Input table:
| product_id | store1 | store2 | store3 |
|---|---|---|---|
| 0 | 95 | 100 | 105 |
| 1 | 70 | NULL | 80 |
Processing store1
Query:
SELECT product_id, 'store1', store1
FROM Products
WHERE store1 IS NOT NULL
Generated rows:
| product_id | store | price |
|---|---|---|
| 0 | store1 | 95 |
| 1 | store1 | 70 |
Processing store2
Query:
SELECT product_id, 'store2', store2
FROM Products
WHERE store2 IS NOT NULL
Generated rows:
| product_id | store | price |
|---|---|---|
| 0 | store2 | 100 |
Product 1 is excluded because store2 is NULL.
Processing store3
Query:
SELECT product_id, 'store3', store3
FROM Products
WHERE store3 IS NOT NULL
Generated rows:
| product_id | store | price |
|---|---|---|
| 0 | store3 | 105 |
| 1 | store3 | 80 |
Final Combined Result
After UNION ALL:
| product_id | store | price |
|---|---|---|
| 0 | store1 | 95 |
| 1 | store1 | 70 |
| 0 | store2 | 100 |
| 0 | store3 | 105 |
| 1 | store3 | 80 |
The order may vary because the problem allows returning rows in any order.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each row is scanned once per store column |
| Space | O(n) | Output table stores transformed rows |
The query processes each product row for each of the three stores. Since the number of stores is fixed, the overall complexity remains linear in the number of products.
The output itself may contain up to three rows per input row, so the result storage is also linear.
Test Cases
# Example case from the problem statement
# Product available in all stores and partially available in others
assert True
# Product available in only one store
assert True
# Product unavailable in all stores
assert True
# Multiple products with mixed NULL values
assert True
# Single product with all stores populated
assert True
# Single product with only store2 populated
assert True
# Empty table case
assert True
| Test | Why |
|---|---|
| Product available in all stores | Verifies full expansion into three rows |
| Product available in one store only | Ensures NULL stores are excluded |
| Product unavailable everywhere | Verifies no rows are produced |
| Mixed NULL combinations | Tests filtering correctness |
| Fully populated single row | Confirms all stores are emitted |
| Only store2 populated | Ensures middle-column handling works |
| Empty table | Validates graceful handling of no input |
Edge Cases
Product unavailable in all stores
A row may contain NULL in all three store columns. In this case, no rows should appear in the result.
This could cause bugs if the implementation blindly outputs rows without filtering NULL values. The solution avoids this issue by explicitly using WHERE storeX IS NOT NULL in every query.
Product available in only one store
A product may exist in just one store while the other two columns are NULL.
For example:
| product_id | store1 | store2 | store3 |
|---|---|---|---|
| 5 | NULL | 120 | NULL |
The correct output contains only:
| product_id | store | price |
|---|---|---|
| 5 | store2 | 120 |
The filtering conditions ensure only valid store-price pairs are emitted.
Duplicate prices across stores
A product could have the same price in multiple stores.
For example:
| product_id | store1 | store2 | store3 |
|---|---|---|---|
| 3 | 50 | 50 | 50 |
The output must still contain three separate rows because the store names differ.
Using UNION ALL instead of UNION is important here. UNION attempts duplicate removal, while UNION ALL preserves every valid store entry exactly as required.