Reducing Dishes LeetCode Solution

Difficulty Level Hard
Frequently asked in American Express
OT SonyViews 6090

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.

Explanation

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.
Every time we add a new dish to the menu list,
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.

Reference: https://en.wikipedia.org/wiki/Dynamic_programming

Translate »