LeetCode 3050 - Pizza Toppings Cost Analysis

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to compute the total cost of all possible three-topping pizza combinations using a list of available toppings from a database table. Each topping has a name and a cost, and toppings are unique. The key requirements are that no topping can be repeated in a combination, toppings must be listed in alphabetical order in the output, and the total cost of each combination should be rounded to two decimal places. The output should be a table with two columns: the pizza combination as a comma-separated string of toppings and the corresponding total cost. Additionally, the output must be sorted first by total cost in descending order, and then alphabetically by the pizza combination.

The input is a table named Toppings with columns topping_name and cost. The table is guaranteed to have unique topping names. The output is a table listing all possible three-topping combinations with their total cost, respecting the ordering rules described.

Important edge cases include scenarios where there are fewer than three toppings, which should return an empty result set, or when multiple toppings have the same cost, which requires careful handling to maintain alphabetical ordering.

Approaches

A brute-force approach would involve generating all possible combinations of three distinct toppings, summing their costs, and then sorting the results. While this approach is correct, it may be inefficient if the number of toppings is large because generating all combinations grows cubically with the number of toppings, specifically O(n³) when using triple nested loops.

The optimal approach leverages SQL joins and the properties of sorted order to generate combinations without repeats and ensures correct alphabetical ordering. By joining the table to itself twice and enforcing constraints to avoid repeated toppings and maintain order, we can generate all valid three-topping combinations in a single query. This approach is efficient for database execution because it leverages indexes and avoids unnecessary iteration in application code.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n³)	Generate all 3-combinations using nested loops, sum costs, then sort.
Optimal	O(n³)	O(n³)	SQL self-joins with constraints to generate all valid combinations, sum and order efficiently.

Algorithm Walkthrough

Start with the Toppings table and alias it as t1.
Join Toppings as t2 where t2.topping_name > t1.topping_name to enforce alphabetical ordering and avoid duplicates.
Join Toppings again as t3 where t3.topping_name > t2.topping_name to continue the ordering and ensure distinct toppings.
For each resulting row (t1, t2, t3), compute the total cost by summing t1.cost + t2.cost + t3.cost.
Concatenate the topping names as t1.topping_name || ',' || t2.topping_name || ',' || t3.topping_name to form the pizza column.
Round the total cost to two decimal places.
Order the results first by total_cost in descending order, then by the pizza string in ascending alphabetical order.
Return the resulting table with pizza and total_cost columns.

This works because the constraints t2.topping_name > t1.topping_name and t3.topping_name > t2.topping_name guarantee that toppings are distinct and always listed in alphabetical order. By summing the costs of the three toppings, we correctly compute the total cost, and the final ordering ensures compliance with the problem's requirements.

Python Solution

# Since this is a SQL problem, Python solution would execute the SQL query
# Here is how it would look using a database connection in Python

import sqlite3
from typing import List, Tuple

def pizza_toppings_cost_analysis(conn: sqlite3.Connection) -> List[Tuple[str, float]]:
    query = """
    SELECT 
        t1.topping_name || ',' || t2.topping_name || ',' || t3.topping_name AS pizza,
        ROUND(t1.cost + t2.cost + t3.cost, 2) AS total_cost
    FROM Toppings t1
    JOIN Toppings t2 ON t2.topping_name > t1.topping_name
    JOIN Toppings t3 ON t3.topping_name > t2.topping_name
    ORDER BY total_cost DESC, pizza ASC;
    """
    cursor = conn.cursor()
    cursor.execute(query)
    return cursor.fetchall()

This Python solution executes the SQL query directly using a database connection. The query generates all valid three-topping combinations, sums their costs, rounds them, and orders the results according to the problem's specifications.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "fmt"
)

func PizzaToppingsCostAnalysis(db *sql.DB) ([][2]interface{}, error) {
    query := `
    SELECT 
        t1.topping_name || ',' || t2.topping_name || ',' || t3.topping_name AS pizza,
        ROUND(t1.cost + t2.cost + t3.cost, 2) AS total_cost
    FROM Toppings t1
    JOIN Toppings t2 ON t2.topping_name > t1.topping_name
    JOIN Toppings t3 ON t3.topping_name > t2.topping_name
    ORDER BY total_cost DESC, pizza ASC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results [][2]interface{}
    for rows.Next() {
        var pizza string
        var totalCost float64
        if err := rows.Scan(&pizza, &totalCost); err != nil {
            return nil, err
        }
        results = append(results, [2]interface{}{pizza, totalCost})
    }
    return results, nil
}

func main() {
    db, _ := sql.Open("sqlite3", "toppings.db")
    defer db.Close()
    results, _ := PizzaToppingsCostAnalysis(db)
    fmt.Println(results)
}

In Go, the approach is the same as Python, but we scan rows into Go variables. The SQL query itself handles the combination generation, cost computation, rounding, and ordering.

Worked Examples

Using the provided toppings:

topping_name	cost
Pepperoni	0.50
Sausage	0.70
Chicken	0.55
Extra Cheese	0.40

Step 1: t1 = Chicken

Step 2: t2 = Extra Cheese, t3 = Pepperoni → pizza = "Chicken,Extra Cheese,Pepperoni", total_cost = 0.55 + 0.40 + 0.50 = 1.45

Step 3: t2 = Extra Cheese, t3 = Sausage → pizza = "Chicken,Extra Cheese,Sausage", total_cost = 1.65

Step 4: t2 = Pepperoni, t3 = Sausage → pizza = "Chicken,Pepperoni,Sausage", total_cost = 1.75

Step 5: t1 = Extra Cheese, t2 = Pepperoni, t3 = Sausage → pizza = "Extra Cheese,Pepperoni,Sausage", total_cost = 1.60

Finally, the result is sorted by total_cost descending and pizza ascending:

pizza	total_cost
Chicken,Pepperoni,Sausage	1.75
Chicken,Extra Cheese,Sausage	1.65
Extra Cheese,Pepperoni,Sausage	1.60
Chicken,Extra Cheese,Pepperoni	1.45

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³)	The query performs a triple self-join, which generates all combinations of three distinct toppings.
Space	O(n³)	Space is used to store all resulting three-topping combinations.

Even though O(n³) appears high, the actual number of toppings in practice is small, so the database can handle the join efficiently.

Test Cases

# Basic test case
assert pizza_toppings_cost_analysis(conn) == [
    ("Chicken,Pepperoni,Sausage", 1.75),
    ("Chicken,Extra Cheese,Sausage", 1.65),
    ("Extra Cheese,Pepperoni,Sausage", 1.60),
    ("Chicken,Extra Cheese,Pepperoni", 1.45)
]  # Provided example

# Fewer than 3 toppings should return empty
# Toppings table has only 2 rows
assert pizza_toppings_cost_analysis(conn) == []

# Duplicate cost values
# Toppings table: [('A', 1.0), ('B', 1.0), ('C', 1.0), ('D', 1.0)]
# Check alphabetical ordering
assert pizza_toppings_cost_analysis(conn) == [
    ("A,B,C", 3.0),
    ("A,B,D", 3.0),
    ("A,C,D", 3.0),
    ("B,C,D", 3.0)
]

Test	Why
Provided example	Validates basic functionality and correct sorting
Fewer than 3 toppings	Checks handling of insufficient input
Duplicate cost values	Ensures alphabetical ordering when costs are equal