1402. Reducing Dishes LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1402. Reducing Dishes LeetCode Solution with the best time and space complexity. The solution to Reducing Dishes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Reducing Dishes solution in C++
Reducing Dishes solution in Java
Reducing Dishes solution in Python
Additional Resources

1402. Reducing Dishes LeetCode Solution image

Problem Statement of Reducing Dishes

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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

1402. Reducing Dishes LeetCode Solution in C++

class Solution {
 public:
  int maxSatisfaction(vector<int>& satisfaction) {
    int ans = 0;
    int sumSatisfaction = 0;

    ranges::sort(satisfaction, greater<>());

    for (const int s : satisfaction) {
      sumSatisfaction += s;
      if (sumSatisfaction <= 0)
        return ans;
      ans += sumSatisfaction;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1402. Reducing Dishes LeetCode Solution in Java

class Solution {
  public int maxSatisfaction(int[] satisfaction) {
    int ans = 0;
    int sumSatisfaction = 0;

    satisfaction = Arrays.stream(satisfaction)
                       .boxed()
                       .sorted(Collections.reverseOrder())
                       .mapToInt(Integer::intValue)
                       .toArray();

    for (final int s : satisfaction) {
      sumSatisfaction += s;
      if (sumSatisfaction <= 0)
        return ans;
      ans += sumSatisfaction;
    }

    return ans;
  }
}
// code provided by PROGIEZ

1402. Reducing Dishes LeetCode Solution in Python

class Solution:
  def maxSatisfaction(self, satisfaction: list[int]) -> int:
    ans = 0
    sumSatisfaction = 0

    for s in sorted(satisfaction, reverse=True):
      sumSatisfaction += s
      if sumSatisfaction <= 0:
        return ans
      ans += sumSatisfaction

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents