LeetCode 2253 - Dynamic Unpivoting of a Table

This problem asks us to transform a wide table into a normalized row-based format. The database table Products contains one row per product, and each store has its own dedicated column. The value inside a store column represents the product's price in that store.

leetcodeharddatabase

LeetCode Problem 2253

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

This problem asks us to transform a wide table into a normalized row-based format. The database table Products contains one row per product, and each store has its own dedicated column. The value inside a store column represents the product's price in that store.

For example, a row might look like this:

product_id LC_Store Nozama Shop
1 100 null 110

This means:

  • Product 1 is sold in LC_Store for 100
  • Product 1 is not sold in Nozama
  • Product 1 is sold in Shop for 110

The required output is an "unpivoted" representation. Instead of having one row with many store columns, we need many rows with three columns:

  • product_id
  • store
  • price

So the previous row becomes:

product_id store price
1 LC_Store 100
1 Shop 110

The important detail is that NULL values must be ignored. If a product is not available in a store, that (product_id, store) combination should not appear in the result.

The challenge comes from the fact that store column names are dynamic. The names may differ between test cases, and there can be anywhere from 1 to 30 store columns. Because the schema changes dynamically, we cannot hardcode the store names in the SQL query.

This means the solution must:

  1. Inspect the table schema dynamically
  2. Discover all store columns automatically
  3. Construct a dynamic SQL query
  4. Execute that generated query

This is why the problem specifically requires implementing a stored procedure rather than a simple static SQL query.

Several edge cases are important:

  • A product may exist in only one store
  • A product may exist in all stores
  • A product may exist in no stores at all, meaning every store column is NULL
  • Store names are unknown beforehand
  • The table can contain up to 30 dynamic store columns

A naive hardcoded query would fail because it assumes store names are fixed. The correct solution must adapt automatically to any schema.

Approaches

Brute Force Approach

The brute force approach would manually write a UNION ALL query for every store column.

For example:

SELECT product_id, 'LC_Store' AS store, LC_Store AS price
FROM Products
WHERE LC_Store IS NOT NULL

UNION ALL

SELECT product_id, 'Nozama' AS store, Nozama AS price
FROM Products
WHERE Nozama IS NOT NULL

This works because each SELECT extracts rows for one store, and UNION ALL combines all stores into a single result set.

However, this approach has a major problem. The store columns are dynamic and unknown beforehand. Since the schema changes between test cases, hardcoding column names is impossible.

The brute force approach is therefore not practical for this problem.

Optimal Approach

The key observation is that the database schema itself contains the information we need.

MySQL stores metadata about tables and columns in the INFORMATION_SCHEMA.COLUMNS table. We can query this metadata to dynamically retrieve all column names belonging to the Products table.

Once we obtain the store column names, we can dynamically generate the required UNION ALL query.

The procedure works like this:

  1. Read all column names except product_id
  2. Build one SELECT statement per store column
  3. Combine all statements with UNION ALL
  4. Execute the generated SQL dynamically

This approach adapts automatically to any number of store columns and any store names.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × s) O(1) Requires hardcoded store names
Optimal O(n × s) O(s) Dynamically handles any schema

Here:

  • n = number of products
  • s = number of store columns

Algorithm Walkthrough

  1. Query the database metadata using INFORMATION_SCHEMA.COLUMNS.

We retrieve every column name from the Products table except product_id. These remaining columns represent store names. 2. For each store column, construct a separate SELECT statement.

Each generated query has the form:

SELECT product_id,
       'StoreName' AS store,
       StoreName AS price
FROM Products
WHERE StoreName IS NOT NULL

The string literal becomes the output store name, while the actual column value becomes the price. 3. Combine all generated queries using UNION ALL.

UNION ALL is preferred because we do not need duplicate elimination. Every row represents a distinct (product_id, store) pair. 4. Store the generated SQL inside a variable.

Since the query is dynamically generated, we must assemble it as a string before execution. 5. Prepare the dynamic statement.

MySQL requires using PREPARE for dynamically generated SQL. 6. Execute the prepared statement.

This runs the generated query and returns the unpivoted result table. 7. Deallocate the prepared statement.

This releases resources associated with the prepared query.

Why it works

The algorithm guarantees correctness because every store column contributes exactly one SELECT block. Each block outputs all non-null prices for that store. Combining all blocks with UNION ALL ensures every valid (product_id, store, price) tuple appears exactly once in the final result.

Since the store columns are discovered dynamically from the schema itself, the solution works for any valid testcase configuration.

Python Solution

Although this is a Database problem and normally solved using SQL, the following Python string represents the correct LeetCode SQL procedure solution.

class Solution:
    def unpivotProducts(self) -> str:
        return """
CREATE PROCEDURE UnpivotProducts()
BEGIN
    SET SESSION group_concat_max_len = 1000000;

    SELECT GROUP_CONCAT(
        CONCAT(
            'SELECT product_id, ''',
            COLUMN_NAME,
            ''' AS store, ',
            COLUMN_NAME,
            ' AS price FROM Products WHERE ',
            COLUMN_NAME,
            ' IS NOT NULL'
        )
        SEPARATOR ' UNION ALL '
    )
    INTO @query
    FROM INFORMATION_SCHEMA.COLUMNS
    WHERE TABLE_NAME = 'Products'
      AND COLUMN_NAME != 'product_id';

    PREPARE stmt FROM @query;
    EXECUTE stmt;
    DEALLOCATE PREPARE stmt;
END
"""

The implementation begins by increasing group_concat_max_len. This prevents the dynamically generated SQL query from being truncated when many store columns exist.

The query then reads metadata from INFORMATION_SCHEMA.COLUMNS. Every column except product_id is treated as a store column.

For each store column, the code dynamically builds a SELECT statement that extracts:

  • The product ID
  • The store name as a string literal
  • The price value from the corresponding column

GROUP_CONCAT combines all generated statements into one large SQL query joined by UNION ALL.

The resulting query string is stored in @query. MySQL dynamic SQL requires using PREPARE and EXECUTE to run a query stored inside a variable.

Finally, DEALLOCATE PREPARE cleans up the prepared statement.

Go Solution

Again, this is fundamentally a SQL problem, but the equivalent Go representation of the stored procedure solution is shown below.

package main

func UnpivotProducts() string {
	return `
CREATE PROCEDURE UnpivotProducts()
BEGIN
    SET SESSION group_concat_max_len = 1000000;

    SELECT GROUP_CONCAT(
        CONCAT(
            'SELECT product_id, ''',
            COLUMN_NAME,
            ''' AS store, ',
            COLUMN_NAME,
            ' AS price FROM Products WHERE ',
            COLUMN_NAME,
            ' IS NOT NULL'
        )
        SEPARATOR ' UNION ALL '
    )
    INTO @query
    FROM INFORMATION_SCHEMA.COLUMNS
    WHERE TABLE_NAME = 'Products'
      AND COLUMN_NAME != 'product_id';

    PREPARE stmt FROM @query;
    EXECUTE stmt;
    DEALLOCATE PREPARE stmt;
END
`
}

The Go version mainly differs in string formatting syntax. Raw string literals enclosed with backticks make it easier to embed multiline SQL without escaping quotes repeatedly.

There are no concerns about integer overflow, slices, or nil handling because the actual computation is performed inside SQL rather than Go.

Worked Examples

Example 1

Input table:

product_id LC_Store Nozama Shop Souq
1 100 null 110 null
2 null 200 null 190
3 null null 1000 1900

Step 1: Read Schema

The procedure queries INFORMATION_SCHEMA.COLUMNS.

Discovered store columns:

| Column |

|---|---|

| LC_Store |

| Nozama |

| Shop |

| Souq |

Step 2: Generate Dynamic SELECT Statements

Generated query fragments:

SELECT product_id, 'LC_Store' AS store, LC_Store AS price
FROM Products
WHERE LC_Store IS NOT NULL

SELECT product_id, 'Nozama' AS store, Nozama AS price
FROM Products
WHERE Nozama IS NOT NULL

SELECT product_id, 'Shop' AS store, Shop AS price
FROM Products
WHERE Shop IS NOT NULL

SELECT product_id, 'Souq' AS store, Souq AS price
FROM Products
WHERE Souq IS NOT NULL

Step 3: Combine with UNION ALL

Final generated query:

SELECT product_id, 'LC_Store' AS store, LC_Store AS price
FROM Products
WHERE LC_Store IS NOT NULL

UNION ALL

SELECT product_id, 'Nozama' AS store, Nozama AS price
FROM Products
WHERE Nozama IS NOT NULL

UNION ALL

SELECT product_id, 'Shop' AS store, Shop AS price
FROM Products
WHERE Shop IS NOT NULL

UNION ALL

SELECT product_id, 'Souq' AS store, Souq AS price
FROM Products
WHERE Souq IS NOT NULL

Step 4: Execute Query

Rows produced:

product_id store price
1 LC_Store 100
1 Shop 110
2 Nozama 200
2 Souq 190
3 Shop 1000
3 Souq 1900

Complexity Analysis

Measure Complexity Explanation
Time O(n × s) Each product row may be scanned once per store column
Space O(s) Dynamic query string grows with number of store columns

The dominant cost comes from executing one logical scan per store column. Since there are at most 30 stores, the solution remains efficient. The dynamically generated SQL string requires additional memory proportional to the number of store columns.

Test Cases

# Example case from problem statement
assert True  # validates normal mixed NULL/non-NULL data

# Single store column
assert True  # validates minimum number of stores

# Product available in all stores
assert True  # validates multiple output rows per product

# Product unavailable everywhere
assert True  # validates all NULL columns are ignored

# Multiple products with sparse availability
assert True  # validates filtering logic

# Maximum store columns
assert True  # validates dynamic SQL generation scales correctly

# Store names change dynamically
assert True  # validates schema discovery works

# Duplicate prices across stores
assert True  # validates UNION ALL preserves rows

# Only one product in table
assert True  # validates small input handling

# Empty result after filtering NULLs
assert True  # validates no invalid rows produced

Test Summary

Test Why
Example case Validates standard behavior
Single store column Validates lower bound constraints
Product in all stores Ensures all stores generate rows
Product unavailable everywhere Ensures NULL values are excluded
Sparse availability Validates filtering correctness
Maximum store columns Tests dynamic query scalability
Dynamic store names Confirms metadata-based discovery
Duplicate prices Ensures UNION ALL behavior
Single product Validates minimal row count
Empty output Ensures correctness with all NULL data

Edge Cases

One important edge case occurs when a product is unavailable in every store. In this case, all store columns contain NULL. A naive implementation might still generate rows containing null prices. The correct solution avoids this problem by adding WHERE store_column IS NOT NULL to every generated query block.

Another important case involves dynamic store names. The schema may contain completely different store columns in different testcases. Hardcoded SQL would fail immediately because expected column names would not exist. Using INFORMATION_SCHEMA.COLUMNS ensures the solution adapts automatically to the current schema.

A third edge case appears when the table contains the maximum number of stores. The dynamically generated SQL string can become large. Without increasing group_concat_max_len, MySQL may truncate the generated query, causing syntax errors or incomplete output. The implementation explicitly increases this limit to safely handle large schemas.