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.length1 <= n <= 500-1000 <= satisfaction[i] <= 1000The key observation in #1402 Reducing Dishes is that each dish contributes a value multiplied by its cooking time index. Therefore, the order in which dishes are cooked greatly impacts the final score. A useful strategy is to sort the satisfaction values and reason about whether adding a dish earlier increases or decreases the total contribution.
A common optimized idea uses a greedy approach after sorting. By considering dishes from the highest satisfaction backward, you can track how adding a dish changes the cumulative sum and overall like-time coefficient. If adding a dish improves the total contribution, it should be included; otherwise it can be skipped.
An alternative way to reason about the problem is through dynamic programming, where each state represents whether to include a dish at a certain time position. However, the greedy insight after sorting typically simplifies the solution.
The dominant cost comes from sorting the array, giving a time complexity of O(n log n) with O(1) or small auxiliary space depending on implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy + Sorting | O(n log n) | O(1) |
| Dynamic Programming | O(n^2) | O(n^2) |
CodeHelp - by Babbar
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming to find the optimal solution by saving the previous best like-time coefficient and its corresponding element sum.
If adding the current element to the previous best like-time coefficient and its corresponding element sum would increase the best like-time coefficient, then go ahead and add it. Otherwise, keep the previous best like-time coefficient.
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) for using a constant amount of extra space.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int maxSatisfaction(std::vector<int>& satisfaction) {
6 std::sort(satisfaction.begin(), satisfaction.end(), std::greater<int>());
7 int total = 0, sum = 0;
8 for (int s : satisfaction) {
9 sum += s;
10 if (sum > 0) {
11 total += sum;
12 } else {
13 break;
14 }
}
return total;
}
int main() {
std::vector<int> satisfaction = {-1, -8, 0, 5, -9};
std::cout << maxSatisfaction(satisfaction);
return 0;
}This C++ solution similarly sorts the satisfaction levels in decreasing order. It then iteratively accumulates the like-time coefficient, stopping when the running sum becomes non-positive.
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.
Time Complexity: O(n^2)
Space Complexity: O(n)
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting helps evaluate dishes in an order that makes the contribution of each dish easier to reason about. Higher satisfaction dishes tend to benefit more when placed earlier, so sorting allows the algorithm to evaluate whether including additional dishes improves the total score.
Yes, problems like Reducing Dishes are common in technical interviews because they test greedy reasoning, sorting strategies, and optimization thinking. Variations of this problem can appear in interviews at large tech companies including FAANG.
The optimal approach typically uses a greedy strategy combined with sorting. By sorting satisfaction values and iterating from the largest values backward, you can decide whether adding a dish increases the total like-time coefficient. This insight reduces the problem to efficient cumulative calculations.
Dynamic programming can solve the problem by modeling choices of including or skipping dishes at different time slots. However, once the greedy insight is discovered, the problem can be solved more efficiently using sorting and prefix sums.
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.