Pizza Toppings Cost Analysis

Problem

Table: Toppings

1
2
3
4
5
6
7
8


+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| topping_name | varchar |
| cost         | decimal |
+--------------+---------+
topping_name is the primary key for this table.
Each row of this table contains topping name and the cost of the topping.

Write a solution to calculate the total cost of all possible3-topping pizza combinations from a given list of toppings. The total cost of toppings must be rounded to 2 decimal places.

Note:

Do not include the pizzas where a topping is repeated. For example, ‘Pepperoni, Pepperoni, Onion Pizza’.
Toppings must be listed in alphabetical order. For example, ‘Chicken, Onions, Sausage’. ‘Onion, Sausage, Chicken’ is not acceptable.

Return the result table ordered by total cost in descending order and combination of toppings inascending order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


Input: 
Toppings table:
+--------------+------+
| topping_name | cost |
+--------------+------+
| Pepperoni    | 0.50 |
| Sausage      | 0.70 |
| Chicken      | 0.55 |
| Extra Cheese | 0.40 |
+--------------+------+
Output: 
+--------------------------------+------------+
| 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       | 
+--------------------------------+------------+
Explanation: 
There are only four different combinations possible with the three topings:
- Chicken, Pepperoni, Sausage: Total cost is $1.75 (Chicken $0.55, Pepperoni $0.50, Sausage $0.70).
- Chicken, Extra Cheese, Sausage: Total cost is $1.65 (Chicken $0.55, Extra Cheese $0.40, Sausage $0.70).
- Extra Cheese, Pepperoni, Sausage: Total cost is $1.60 (Extra Cheese $0.40, Pepperoni $0.50, Sausage $0.70).
- Chicken, Extra Cheese, Pepperoni: Total cost is $1.45 (Chicken $0.55, Extra Cheese $0.40, Pepperoni $0.50).
Output table is ordered by the total cost in descending order.

Solution

Method 1 - Triple Self-Join (Combinatorial SQL)

Intuition

We need to generate all unique 3-topping combinations, sum their costs, and output the results sorted by total_cost (descending) and pizza name (ascending). This is a classic self-join/combinatorics problem in SQL, and a combinations problem in pandas. Use t1, t2, t3 aliases to enforce alphabetical ordering on topping_name.

Approach

Use a triple self-join on the Toppings table (with t1, t2, t3 aliases) and enforce alphabetical order via t1.topping_name < t2.topping_name < t3.topping_name to generate all unique pizza combinations.
Sum the cost columns, round to 2 decimals into total_cost, and concatenate the topping_names in alphabetical order to produce the pizza string.
Sort the result by total_cost descending and pizza ascending.

Code

1
2
3
4
5
6
7


SELECT
  CONCAT(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 t1.topping_name < t2.topping_name
JOIN Toppings t3 ON t2.topping_name < t3.topping_name
ORDER BY total_cost DESC, pizza ASC;

1
2
3
4
5
6
7


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 t1.topping_name < t2.topping_name
JOIN Toppings t3 ON t2.topping_name < t3.topping_name
ORDER BY total_cost DESC, pizza ASC;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


import pandas as pd
from itertools import combinations

def pizza_toppings_cost_analysis(toppings: pd.DataFrame) -> pd.DataFrame:
    combos = []
    for c in combinations(sorted(toppings['topping_name']), 3):
        costs = toppings.set_index('topping_name').loc[list(c), 'cost']
        pizza = ','.join(c)
        total_cost = round(costs.sum(), 2)
        combos.append((pizza, total_cost))
    df = pd.DataFrame(combos, columns=['pizza', 'total_cost'])
    return df.sort_values(['total_cost', 'pizza'], ascending=[False, True]).reset_index(drop=True)

Complexity

⏰ Time complexity: O(n^3) (where n is the number of toppings; for small n this is acceptable)
🧺 Space complexity: O(n^3) (for storing all combinations)

Problem#

Examples#

Solution#

Method 1 - Triple Self-Join (Combinatorial SQL)#

Intuition#

Approach#

Code#

Complexity#