# Reducing Dishes LeetCode Solution

Difficulty Level Hard
OT SonyViews 5802

## Problem Statement

Reducing Dishes LeetCode Solution – A chef has collected data on the `satisfaction` level of his `n` dishes. A 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 the like-time coefficient that the chef can obtain after dishes preparation.

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

```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.```

## Intuition

If we cook some dishes, they must be the most satisfactory among all choices.

Another important observation is that we will cook the dish with small satisfaction, and leave the most satisfying dish in the end.

We choose dishes from the most satisfied.
all dishes on the menu list will be cooked one-time unit later,
so the `result += total satisfaction on the list`.
We’ll keep doing this as long as `A[i] + total > 0`.

Approach:

The basic observation required to solve the problem is that the more dishes you add the more the total time T spent on other dishes which is exactly what we want as we need to maximize the sum of this `T * satisfaction[i]` for some values of `0 <= i < satisfaction.length`. Since satisfaction value can be `-ve` also so if all satisfaction value is `-ve` then no matter how much time we spend on one dish the result will always be 0 i.e., the maximum sum of the Like-time coefficient that the chef can obtain after dishes preparation should be 0. Also, since the dishes can be prepared in any order, we would like to sort the dishes by their satisfaction value.

Note that we can’t just skip all `-ve` values and start with the first non-negative value as the more dishes we include the greater will be the value of the coefficient of satisfaction. Since we might need to choose some `-ve` values also so a recursive approach can be as follows:

1. sort the satisfaction array.
2. keep a counter, say `cnt` which starts from 0. `cnt` will indicate how much time has already been spent or how many dishes have already been considered. One and the same thing as 1 dish takes 1 unit of time.
3. for every index, `i` we can either choose the dish in which case the value will be `(cnt+1)*satisfaction[i]` , or we skip to the next dish and follow the same idea mentioned at this point.

This leads to a recursive approach, a DP solution for which is as:

## Code

### C++ Code for Reducing Dishes

```class Solution {
public:
int maxSatisfaction(vector<int>& A) {
sort(A.begin(), A.end());
int res = 0, total = 0, n = A.size();
for (int i = n - 1; i >= 0 && A[i] > -total; --i) {
total += A[i];
res += total;
}
return res;
}
};```

### Java Code for Reducing Dishes

```class Solution {
public int maxSatisfaction(int[] A) {
Arrays.sort(A);
int res = 0, total = 0, n = A.length;
for (int i = n - 1; i >= 0 && A[i] > -total; --i) {
total += A[i];
res += total;
}
return res;
}
}```

### Python Code for Reducing Dishes

```class Solution:
def maxSatisfaction(self, A):
res = total = 0
A.sort()
while A and A[-1] + total > 0:
total += A.pop()
res += total
return res
```

## Complexity Analysis for Reducing Dishes LeetCode Solution

### Time Complexity

O(NlogN) since sorting is taking place.

### Space Complexity

O(1) as we are not using any extra space.

Translate »