Reducing Dishes: Greedy Sorting for Maximum Satisfaction

A chef has collected data on the satisfaction level of his n dishes. In one unit of time, the chef can cook any dish. The "like-time coefficient" of a dish is the time taken to cook that dish multiplied by its satisfaction level: time[i] * satisfaction[i]. Return the maximum sum of like-time coefficients the chef can achieve. Dishes can be prepared in any order, and the chef can discard some dishes to maximize the result.

This is LeetCode 1402: Reducing Dishes, a hard problem that looks like it needs dynamic programming but actually collapses into a clean greedy solution once you see the core insight about how adding a dish shifts all time slots.

Why this problem matters

Reducing Dishes is a great example of a problem where sorting unlocks a greedy strategy. Many candidates reach for DP when they see "maximize" in the problem statement, but the structure of the time multipliers means a much simpler approach works. Recognizing when greedy is sufficient, and why it is correct, is an important skill for interviews.

The pattern of sorting, then greedily building a solution while tracking a running sum, shows up in problems like Assign Cookies, Candy, and many interval scheduling problems. Getting comfortable with the reasoning here makes those problems feel more natural.

The brute force approach

The most direct approach is to try every possible subset of dishes, arrange each subset optimally, and take the maximum.

def max_satisfaction_brute(satisfaction):
    n = len(satisfaction)
    best = 0
    for mask in range(1 << n):
        subset = sorted([satisfaction[i] for i in range(n) if mask & (1 << i)])
        total = sum((t + 1) * s for t, s in enumerate(subset))
        best = max(best, total)
    return best

This checks all 2^n subsets and sorts each one. The time complexity is O(2^n * n log n), which is far too slow for n up to 500. We need a fundamentally different approach.

The key insight: sort and add greedily

Sort the satisfaction array in descending order. Now consider building the solution from the most satisfying dish to the least satisfying. Each time you include a new dish (prepending it to the sequence), every previously included dish shifts one time slot to the right. That shift increases each of their contributions by exactly their satisfaction value. So the total increase from including a new dish equals the running sum of all currently included satisfactions, plus the new dish's satisfaction.

As long as the running sum stays positive after including a dish, the overall total keeps growing. The moment the running sum goes negative, every future dish (which has an even lower satisfaction) would make it worse. Stop there.

Walking through it step by step

Let's trace through satisfaction = [-1, -8, 0, 5, -9]. The answer is 14.

The greedy logic stops at -8 because including it would make the running sum negative. Every dish after -8 is even more negative, so there is no point in continuing.

The greedy solution

Here is the complete solution in Python:

def max_satisfaction(satisfaction):
    satisfaction.sort(reverse=True)
    total = 0
    running_sum = 0
    for s in satisfaction:
        running_sum += s
        if running_sum > 0:
            total += running_sum
        else:
            break
    return total

Here is what each piece does:

1. Sort descending. This ensures we consider the most satisfying dishes first. Dishes with higher satisfaction should occupy later time slots (larger multipliers), which naturally happens when we prepend dishes to the sequence.
2. Track running_sum. This is the cumulative sum of all included satisfaction values. Each time we include a new dish, every previously included dish gets its time slot bumped by 1, contributing running_sum additional total.
3. Track total. Each time we include a dish, we add running_sum to total. This accounts for both the new dish's contribution and the increased contributions of all previously included dishes.
4. Stop when running_sum goes non-positive. Once the cumulative satisfaction is zero or negative, including more dishes (which are even less satisfying) can only decrease the total.

Why the greedy approach is optimal

The key observation is mathematical. Suppose you have already included dishes with satisfactions s1, s2, ..., sk (in descending order). The total like-time coefficient is 1*sk + 2*s(k-1) + ... + k*s1. Now consider including the next dish s(k+1). Every existing dish's time slot increases by 1, so their combined contribution grows by s1 + s2 + ... + sk = running_sum. The new dish itself contributes 1 * s(k+1). The net change is running_sum + s(k+1), which is exactly the new running_sum.

If this new running sum is positive, the total increased. If it is zero or negative, the total did not improve, and since all remaining dishes have even smaller satisfaction values, no future inclusion can help either. This monotonicity is what makes the greedy choice provably optimal.

Complexity analysis

The loop itself is O(n). The bottleneck is sorting. Since we need to consider dishes in order of satisfaction, sorting is unavoidable. O(n log n) is optimal for this problem.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Sort-then-greedy

The pattern of sorting the input to reveal a greedy structure:

items.sort(key=some_criterion)
result = initial_value
for item in items:
    if greedy_condition(item, state):
        update(result, item)
    else:
        break

In Reducing Dishes, the sort criterion is descending satisfaction, and the greedy condition is whether the running sum remains positive. In Assign Cookies, you sort both children and cookies, then greedily match them. In Non-overlapping Intervals, you sort by end time and greedily skip overlaps. The skeleton is the same: sort to create a predictable order, then scan with a simple condition.

2. Running sum tracking

The idea of maintaining a cumulative value that tells you whether the next greedy step is still beneficial:

running = 0
for value in sorted_values:
    running += value
    if running > threshold:
        accumulate(running)
    else:
        break

This micro-pattern shows up whenever adding the next element has a cascading effect on all previous elements. The running sum captures that cascade in a single variable, turning what looks like an O(n^2) recalculation into O(1) per step.

Edge cases

Before submitting, make sure your solution handles these:

• All negative satisfactions [-5, -3, -1]: the running sum starts negative immediately. The chef should cook zero dishes. Return 0.
• All positive satisfactions [1, 2, 3]: every dish is worth including. The loop never breaks early. Total = 1(1) + 2(2) + 3(3) = 14.
• Single dish, positive [5]: running_sum = 5, total = 5. Cook it at time 1.
• Single dish, negative [-3]: running_sum = -3, stop immediately. Return 0.
• Mix with zero [0, 0, 0]: running_sum stays at 0, which is not greater than 0, so we stop. Return 0. Including zero-satisfaction dishes adds nothing.
• Already sorted [5, 3, 1]: the sort is a no-op. The algorithm still works correctly.

The greedy solution handles all of these without special-case logic.

Common mistakes

1. Sorting in ascending order instead of descending. The greedy logic requires that we consider the most satisfying dishes first. Sorting ascending and scanning from the end works too, but if you scan from the front of an ascending array, the running sum logic breaks.

2. Forgetting that the chef can discard dishes. Some people try to include all dishes. The whole point is that negative-satisfaction dishes might not be worth cooking, even at early time slots. The break when running_sum goes non-positive is what handles discarding.

3. Using >= 0 instead of > 0 for the running sum check. If the running sum equals exactly 0, including the dish adds 0 to the total. It does not help, and it makes the running sum no longer positive. Continuing past this point risks decreasing the total on the next iteration. Using > 0 is safer and correct.

4. Trying DP when greedy suffices. A 2D DP with states for "number of dishes included" and "current index" works but runs in O(n^2) time and uses O(n^2) space. The greedy approach is O(n log n) time and O(1) space. Recognizing when greedy is enough is part of the skill.

From understanding to recall

You have read the greedy solution and the math behind it makes sense. Sort descending, track a running sum, accumulate while positive. Three variables, one loop, done. But can you write it from scratch in an interview without looking at it?

The details matter: sorting in reverse, using running_sum > 0 (not >= 0), adding running_sum to total (not s), and breaking immediately when the condition fails. These are small but critical, and they are easy to confuse under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the sort-then-greedy loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize a weighted sum by selecting a subset" and the code flows out without hesitation.

The sort-then-greedy pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Assign Cookies - Another sort-then-greedy problem where sorting both inputs reveals an optimal matching strategy
• Candy - A hard greedy problem that uses two-pass constraint satisfaction, showing how greedy reasoning scales to more complex setups
• Sort Colors - A different kind of sorting problem where the greedy insight is a three-pointer partition instead of a traditional sort

CodeBricks breaks the Reducing Dishes problem into its sort-then-greedy and running sum tracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy optimization question shows up in your interview, you do not think about it. You just write it.