LeetCode 2252 - Dynamic Pivoting of a Table

This problem requires implementing a SQL-style pivot operation programmatically. The input is a table named Products with columns productid, store, and price, where each row represents the price of a product in a specific store.

leetcodeharddatabase

LeetCode Problem 2252

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

This problem requires implementing a SQL-style pivot operation programmatically. The input is a table named Products with columns product_id, store, and price, where each row represents the price of a product in a specific store. The table has a compound primary key (product_id, store) and at most 30 unique stores.

The goal is to reorganize the data so that each row corresponds to a single product_id, and each column (except product_id) corresponds to a store. The value in each store column is the price of the product in that store, or null if the product is not sold there. Store columns must be sorted in lexicographical order. The resulting table can be returned in any row order.

Constraints indicate the number of stores is small (≤30), which allows us to use pivoting techniques without worrying about excessive memory or performance costs. Key edge cases include products that are sold in only a subset of stores, a store with no products, or multiple products sold in the same subset of stores.

Approaches

The brute-force approach is to manually iterate through all products and all possible stores, filling in the price or null if the product is missing from a store. While this works, it requires nested loops: one for products and one for stores, resulting in an O(n*m) time complexity where n is the number of products and m is the number of stores. This is acceptable here because the dataset is small, but it is not elegant or scalable.

The optimal approach leverages dynamic pivoting by first identifying all unique stores and sorting them lexicographically. Then we aggregate prices for each product using a dictionary-like structure or SQL-style conditional expressions. This ensures we only iterate over the dataset once and directly map store names to price values in the output, making the solution clean, maintainable, and performant.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*m) O(n*m) Iterate over products and stores, manually assigning prices
Optimal O(n + m*log m) O(n*m) Extract stores, sort lexicographically, pivot data with dictionary mapping

Algorithm Walkthrough

  1. Extract unique stores from the table and sort them lexicographically. This ensures the output columns appear in the required order.
  2. Initialize a dictionary mapping each product_id to another dictionary that maps store names to prices. This allows quick lookups and assignment.
  3. Iterate through each row of the input table, and populate the inner dictionary for the corresponding product_id with the price at that store.
  4. Generate the output table by iterating through all product_ids. For each product, construct a row starting with product_id followed by prices for each store in sorted order, using null if the store has no entry.
  5. Return the resulting table, which now has a dynamic number of columns corresponding to the sorted store names.

Why it works: The algorithm guarantees that every product gets a row and every store gets a column. The dictionary structure ensures quick access and default handling for missing store entries, preserving correctness. Sorting stores lexicographically guarantees the column order requirement.

Python Solution

from typing import List, Optional

class Solution:
    def PivotProducts(self, products: List[List]) -> List[List[Optional[int]]]:
        # Step 1: Extract unique stores and sort lexicographically
        stores = sorted({row[1] for row in products})
        
        # Step 2: Build product_id -> store -> price mapping
        product_map = {}
        for product_id, store, price in products:
            if product_id not in product_map:
                product_map[product_id] = {}
            product_map[product_id][store] = price
        
        # Step 3: Construct the pivoted table
        result = []
        for product_id in product_map:
            row = [product_id]
            for store in stores:
                row.append(product_map[product_id].get(store, None))
            result.append(row)
        
        return result

The Python implementation follows the algorithm closely. First, we extract and sort stores. Then we populate a nested dictionary where the outer key is product_id and the inner key is the store name, mapping to the price. Finally, we construct each row by iterating through the sorted stores and using .get() to handle missing prices as None.

Go Solution

package main

func PivotProducts(products [][]interface{}) [][]interface{} {
    storeSet := make(map[string]bool)
    productMap := make(map[int]map[string]int)
    
    // Step 1: Collect stores and map products
    for _, row := range products {
        productID := row[0].(int)
        store := row[1].(string)
        price := row[2].(int)
        storeSet[store] = true
        if _, exists := productMap[productID]; !exists {
            productMap[productID] = make(map[string]int)
        }
        productMap[productID][store] = price
    }
    
    // Step 2: Sort stores lexicographically
    stores := make([]string, 0, len(storeSet))
    for store := range storeSet {
        stores = append(stores, store)
    }
    sort.Strings(stores)
    
    // Step 3: Build pivoted table
    result := make([][]interface{}, 0, len(productMap))
    for productID, storePrices := range productMap {
        row := make([]interface{}, 0, len(stores)+1)
        row = append(row, productID)
        for _, store := range stores {
            if price, ok := storePrices[store]; ok {
                row = append(row, price)
            } else {
                row = append(row, nil)
            }
        }
        result = append(result, row)
    }
    
    return result
}

Go requires explicit type handling. We use interface{} for generic handling of integers and nil. The dictionary structure is implemented with nested maps, and missing entries are assigned nil. Sorting uses the standard library sort.Strings.

Worked Examples

For the provided example, we first extract stores: {"Shop", "LC_Store", "Nozama", "Souq"}. Sorting lexicographically gives ["LC_Store", "Nozama", "Shop", "Souq"].

Constructing product_map:

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

Iterating through each product, we build rows using the sorted store order, assigning null for missing stores. The result matches the expected output.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m*log m) O(n) for building the product map, O(m*log m) for sorting stores (m ≤ 30, negligible)
Space O(n*m) Nested dictionary stores price for each product and each store

The time complexity is dominated by the number of products n and stores m. Sorting stores is negligible due to small m. Space is proportional to the number of products times the number of stores.

Test Cases

# Single example from the problem
assert Solution().PivotProducts([
    [1, "Shop", 110],
    [1, "LC_Store", 100],
    [2, "Nozama", 200],
    [2, "Souq", 190],
    [3, "Shop", 1000],
    [3, "Souq", 1900]
]) == [
    [1, 100, None, 110, None],
    [2, None, 200, None, 190],
    [3, None, None, 1000, 1900]
]

# Product missing all stores except one
assert Solution().PivotProducts([
    [1, "Shop", 50]
]) == [
    [1, None, 50]  # if stores are ["LC_Store", "Shop"]
]

# Multiple products same store
assert Solution().PivotProducts([
    [1, "Shop", 50],
    [2, "Shop", 60]
]) == [
    [1, 50],
    [2, 60]
]

# No products
assert Solution().PivotProducts([]) == []

# All products sold in all stores
assert Solution().PivotProducts([
    [1, "A", 10],
    [1, "B", 20],
    [2, "A", 30],
    [2, "B", 40]
]) == [
    [1, 10, 20],
    [2, 30, 40]
]
Test Why
Example Validates standard pivot behavior
Single store Handles missing stores correctly
Multiple products same store Validates multiple rows for same store
Empty input Handles edge case of no products
Full coverage Tests scenario where every product has every store

Edge Cases

One important edge case is when a product exists in only one store. This can lead to missing columns for other stores; our implementation handles this