Skip to main content
Talentd

Reducing Dishes - Solution & Explanation

HardArrayDynamic ProgrammingGreedySorting18 min readAsked at: Microsoft, Google, TCS
Practice this problem

Problem Statement

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].

Return the maximum sum of like-time coefficient that the chef can obtain after preparing some amount of dishes.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

 

Example 1:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

Example 2:

Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3:

Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.

 

Constraints:

  • n == satisfaction.length
  • 1 <= n <= 500
  • -1000 <= satisfaction[i] <= 1000

Approach Overview

Problem Overview: You receive an array where satisfaction[i] represents the satisfaction level of cooking a dish. Each dish cooked at time t contributes satisfaction[i] * t to the total like-time coefficient. You can discard dishes and reorder the rest. The goal is to maximize the final score.

Approach 1: Sorting and Selecting Positive Coefficients (Greedy) (Time: O(n log n), Space: O(1))

The key observation: cooking dishes with larger satisfaction later multiplies them by larger time values. Start by sorting the array so negative values appear first and positive values last. Instead of constructing the order forward, iterate from the end and keep a running suffix sum. Each time you add a dish to the front, the contribution increases by the current total satisfaction of all chosen dishes.

If adding a dish makes the cumulative sum negative, further additions will only reduce the result. Stop immediately. This greedy strategy works because adding dishes with positive cumulative impact always increases every future coefficient. Sorting ensures we always test dishes in the most profitable order.

This approach mainly relies on array traversal and sorting. After sorting, a single backward pass determines which prefix of dishes should be kept. The result accumulates using the running sum technique. Because we only track two integers (running sum and result), the extra memory usage stays constant.

Approach 2: Dynamic Programming (Time: O(n^2), Space: O(n^2))

A dynamic programming formulation treats each dish as a decision: cook it or skip it. After sorting the satisfaction array, define dp[i][t] as the maximum score achievable starting from index i when the next cooking time is t. Two transitions exist: skip the dish (dp[i+1][t]) or cook it (satisfaction[i] * t + dp[i+1][t+1]).

The recursion explores every combination of including or excluding dishes while increasing the time multiplier only when a dish is cooked. Memoization or bottom‑up tabulation prevents recomputation. The DP guarantees correctness because it explicitly evaluates all valid subsets and orders after sorting.

This method is useful for understanding the structure of the problem. It makes the optimization decision explicit and mirrors the mathematical definition of the like-time coefficient. However, the quadratic state space makes it slower and heavier than the greedy insight.

Recommended for interviews: The greedy solution is what most interviewers expect. Recognizing that the optimal set of dishes forms a suffix after sorting demonstrates strong problem‑solving intuition. Explaining the DP formulation first can show full understanding, but implementing the greedy approach proves you can reduce the problem to its optimal O(n log n) solution.

Approach 1: Approach 1: Sorting and Selecting Positive Coefficients

To maximize the like-time coefficient, we can sort the satisfaction levels in non-descending order and calculate the possible like-time coefficients by considering prefixes from the end of the sorted array. This allows us to selectively choose higher satisfaction dishes to maximize the total like-time coefficient.

This C program sorts the satisfaction array in decreasing order and iteratively calculates the like-time coefficient. If adding the current satisfaction level to the sum results in a non-positive value, the computation stops as it indicates that further additions would only decrease the total result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) for using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming

An alternative approach involves using dynamic programming to maximize the like-time coefficient. We maintain a DP table where `dp[i]` represents the maximum like-time coefficient attainable using the first `i` dishes. This approach computes overlap coefficients dynamically using state transitions calculated for each dish considered.

This C solution employs dynamic programming by initializing a DP array with zero and iteratively updating it by considering the choice of including a dish or not, thereby maximizing the like-time coefficient.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Greedy + Sorting

Suppose we only choose one dish, then we should choose the dish with the highest satisfaction s_0, and check whether s_0 is greater than 0. If s_0 leq 0, then we don't cook any dishes, otherwise, we cook this dish, and the total satisfaction is s_0.

If we choose two dishes, then we should choose the two dishes with the highest satisfaction s_0 and s_1, and the satisfaction is s_1 + 2 times s_0. At this time, we need to ensure that the satisfaction after the selection is greater than the satisfaction before the selection, that is, s_1 + 2 times s_0 > s_0, which means as long as s_1 + s_0 > 0, we can choose these two dishes.

By analogy, we can find a rule, that is, we should choose the k dishes with the highest satisfaction, and ensure that the sum of the satisfaction of the first k dishes is greater than 0.

In implementation, we can first sort the satisfaction of all dishes, and then start choosing from the dish with the highest satisfaction. Each time we add the satisfaction of the current dish, if the result of the addition is less than or equal to 0, then we no longer choose the dishes behind, otherwise, we choose this dish.

The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Selecting Positive Coefficients

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) for using a constant amount of extra space.

Approach 2: Dynamic Programming

Time Complexity: O(n^2)
Space Complexity: O(n)

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Greedy Suffix SumO(n log n)O(1)Best practical solution. Use when you recognize the positive cumulative contribution insight.
Dynamic ProgrammingO(n^2)O(n^2)Useful for reasoning about include/skip decisions or explaining the optimal structure.

Video Solution

Reducing Dishes - (MICROSOFT) | Leetcode-1402 | 2 Approaches | Explanation ➕ Live Coding • codestorywithMIK • 10,177 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Reducing Dishes easy or hard?
Reducing Dishes is labeled Hard on LeetCode because the optimal greedy insight is not obvious. Many candidates initially attempt dynamic programming. Recognizing that only dishes with a positive cumulative contribution should be kept reduces the problem to a simple sorted traversal.
Reducing Dishes Python/Java solution
In Python or Java, first sort the satisfaction array. Iterate from the end, maintain a running sum of selected dishes, and accumulate it into the result while the sum stays positive. This implementation is short, uses constant extra space, and runs in O(n log n) time.
How to solve Reducing Dishes in O(n)?
If the array were already sorted, the greedy suffix-sum strategy runs in O(n). Traverse from the end, maintain a running total of satisfaction values, and keep adding dishes while the cumulative sum remains positive. Each addition increases the overall like-time coefficient.
What is the best approach for Reducing Dishes?
The optimal approach is a greedy strategy after sorting the satisfaction array. Iterate from the largest value backward while maintaining a running suffix sum. As long as the cumulative sum stays positive, adding the dish increases the total like-time coefficient. This runs in O(n log n) time due to sorting and O(1) extra space.
Is Reducing Dishes asked at Google/Amazon/Meta?
Reducing Dishes is a classic greedy optimization problem and has appeared in interview preparation lists associated with companies like Google, Amazon, and Meta. It tests recognition of cumulative contribution patterns and the ability to convert a DP-style problem into a greedy solution.
What data structure is used in Reducing Dishes?
The solution primarily uses arrays and sorting. The greedy method relies on iterating through a sorted array while maintaining running sums. The alternative approach uses a dynamic programming table to store states representing index and cooking time.
What is the time complexity of Reducing Dishes?
The optimal greedy solution runs in O(n log n) time because the array must be sorted first. After sorting, a single backward traversal computes the result in O(n). The dynamic programming alternative takes O(n^2) time and O(n^2) space.

Ready to solve this problem?

Practice Reducing Dishes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays