Reducing Dishes - Solution & Explanation

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.