Pizza Toppings Cost Analysis - Solution & Explanation

Problem Overview: You are given a table of pizza toppings with their costs. The task is to generate valid topping combinations and compute the total price for each pizza configuration while avoiding duplicate permutations of the same toppings.

Approach 1: Conditional Self Join (Baseline SQL Strategy) (Time: O(n^3), Space: O(1))

The straightforward SQL strategy is joining the Toppings table with itself multiple times to generate combinations. Each join represents one topping in the pizza. To avoid duplicate permutations such as (pepperoni, cheese, olives) and (cheese, pepperoni, olives), apply ordering constraints like t1.id < t2.id < t3.id. This conditional join ensures each set of toppings appears exactly once. After generating the combination, compute the total cost using t1.cost + t2.cost + t3.cost and return the result sorted by total price and topping names.

This technique works because relational joins can enumerate combinations efficiently without explicit iteration logic. However, the query grows more complex as the number of toppings per pizza increases. The database engine effectively performs a combinational join, which conceptually behaves like O(n^3) for three toppings.

Approach 2: Window Function + Conditional Join (Optimized SQL Pattern) (Time: O(n^3), Space: O(n))

A cleaner approach assigns a deterministic order to toppings using a window function such as ROW_NUMBER(). The query first ranks toppings with ROW_NUMBER() OVER(ORDER BY topping_name). These row numbers act as stable indices. The table is then joined to itself with conditions like a.rn < b.rn AND b.rn < c.rn to construct unique triples.

The key insight is that window functions provide a predictable ordering independent of primary keys. This simplifies combination logic and prevents duplicates without complicated string comparisons. The join then aggregates the cost across the three selected toppings and returns the formatted pizza description along with the total cost.

This pattern appears frequently in advanced SQL and database interview problems where combinations must be generated while enforcing uniqueness. Window functions make the logic explicit and easier to maintain. Many engineers prefer this version because the ranking step separates ordering from the join logic.

Recommended for interviews: Interviewers usually expect the conditional self‑join idea first since it demonstrates understanding of SQL joins and combination constraints. The window function version shows stronger SQL fluency and familiarity with analytical features from window functions. Both approaches produce the same result, but the ranked join pattern tends to be clearer and more scalable in real systems.