LeetCode 1402 - Reducing Dishes

LeetCode Problem 1402

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Greedy, Sorting

Solution

Problem Understanding

In this problem, we are given an integer array called satisfaction, where each element represents the satisfaction level of a dish prepared by a chef. The chef can cook dishes in any order, and each dish takes exactly one unit of time to prepare.

The important detail is how the score is calculated. If a dish is cooked at time t, its contribution to the final score is:

t * satisfaction[i]

The total score is the sum of these contributions across all selected dishes.

The chef is also allowed to discard dishes entirely. This is critical because dishes with negative satisfaction may reduce the total score if included at the wrong time, or at all.

The task is to compute the maximum possible total like-time coefficient.

The input size is relatively small:

• 1 <= n <= 500
• -1000 <= satisfaction[i] <= 1000

Since n is only 500, an O(n^2) dynamic programming solution is feasible. However, the problem has an even better greedy solution after sorting.

A few important observations emerge immediately:

• Positive dishes are usually beneficial because larger cooking times multiply their positive values.
• Negative dishes may still be useful if adding them shifts large positive dishes to later times.
• If all dishes are negative, the best answer is 0, meaning cook nothing.
• The order matters greatly because later positions receive larger multipliers.

For example, if we cook dishes [2,3,4]:

1*2 + 2*3 + 3*4 = 20

But a different order produces a different result:

1*4 + 2*3 + 3*2 = 16

So the problem is fundamentally about selecting an optimal subset and arranging it optimally.

Approaches

Brute Force Approach

The brute force solution considers every possible subset of dishes and every possible ordering of those dishes.

For each subset:

1. Generate all permutations.
2. Compute the total like-time coefficient.
3. Track the maximum score seen.

This works because it exhaustively checks every valid cooking plan, guaranteeing the optimal answer.

However, it is computationally impossible for the given constraints. With n dishes:

• There are 2^n subsets.
• Each subset can have factorially many permutations.

The complexity becomes roughly:

O(2^n * n!)

which is far beyond feasible even for relatively small inputs.

Key Insight for the Optimal Solution

The crucial observation is that sorting changes the structure of the problem dramatically.

Suppose the dishes are sorted in ascending order:

[-9, -8, -1, 0, 5]

Now imagine building the cooking schedule from right to left.

If we already selected some dishes, adding a new dish to the front increases the cooking time of every existing dish by 1. Therefore, adding a dish changes the total score by:

current_sum_of_selected_dishes + new_dish_value

More specifically:

• Let suffix_sum be the sum of currently selected dishes.
• If adding a new dish keeps suffix_sum > 0, the total score increases.
• If the running sum becomes non-positive, adding more dishes only hurts the result.

This leads to a greedy strategy:

1. Sort the array.
2. Traverse from largest satisfaction to smallest.
3. Maintain a running suffix sum.
4. Keep adding dishes while the suffix sum remains positive.

This works because larger dishes benefit most from receiving larger multipliers, and the sorted order naturally maximizes that effect.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n!)	O(n)	Tries every subset and permutation
Optimal Greedy	O(n log n)	O(1) extra space	Sorts and greedily includes beneficial dishes

Algorithm Walkthrough

Optimal Greedy Algorithm

1. Sort the satisfaction array in ascending order.

Sorting is important because we want larger satisfaction values to appear later in the cooking order, where they receive larger time multipliers. 2. Initialize three variables:

• suffix_sum = 0
• total_score = 0
• best_score = 0

The suffix_sum represents the sum of dishes currently selected. 3. Traverse the sorted array from right to left.

This means we start with the largest satisfaction values first. 4. Add the current dish to suffix_sum.

Conceptually, we are inserting this dish at the beginning of the schedule. 5. Check whether suffix_sum is positive.

If it is positive, adding this dish improves the final result because all previously selected dishes shift one time unit later and gain additional contribution. 6. If suffix_sum > 0:

• Add suffix_sum to total_score
• Update best_score

7. If suffix_sum <= 0:

• Stop processing immediately.
• Any smaller values to the left will only decrease the score further.

8. Return best_score.

Why it works

The greedy invariant is:

A dish should only be added if its inclusion increases the total contribution of the schedule.

When inserting a dish at the front, every already-selected dish gains one additional multiplier. Therefore, the net improvement equals the sum of all selected dishes after insertion.

If this sum becomes non-positive, the total score no longer improves. Since the array is sorted, all remaining dishes are even smaller, so continuing cannot help. This guarantees optimality.

Python Solution

from typing import List

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()

        suffix_sum = 0
        total_score = 0
        best_score = 0

        for i in range(len(satisfaction) - 1, -1, -1):
            suffix_sum += satisfaction[i]

            if suffix_sum <= 0:
                break

            total_score += suffix_sum
            best_score = max(best_score, total_score)

        return best_score

The implementation begins by sorting the array in ascending order. This ensures that larger satisfaction values naturally end up later in the cooking sequence where they receive larger multipliers.

The loop iterates from right to left because we want to consider adding larger dishes first. The variable suffix_sum tracks the sum of all currently selected dishes.

When we prepend a dish to the schedule, every already-selected dish shifts one position later. That means the total increase in score equals the current suffix_sum.

If suffix_sum becomes non-positive, the algorithm immediately stops because adding even smaller dishes cannot improve the result.

The variable total_score accumulates the contribution of all chosen dishes, and best_score stores the maximum value seen.

Go Solution

package main

import "sort"

func maxSatisfaction(satisfaction []int) int {
	sort.Ints(satisfaction)

	suffixSum := 0
	totalScore := 0
	bestScore := 0

	for i := len(satisfaction) - 1; i >= 0; i-- {
		suffixSum += satisfaction[i]

		if suffixSum <= 0 {
			break
		}

		totalScore += suffixSum

		if totalScore > bestScore {
			bestScore = totalScore
		}
	}

	return bestScore
}

The Go implementation follows the exact same logic as the Python version.

The built-in sort.Ints function sorts the slice in ascending order. Go slices already behave dynamically, so no special array handling is needed.

The constraints guarantee that integer overflow is not an issue for Go's standard int type because the maximum possible score remains comfortably within bounds.

Unlike Python, Go requires explicit variable declarations and manual maximum comparisons.

Worked Examples

Example 1

Input:

[-1,-8,0,5,-9]

After sorting:

[-9,-8,-1,0,5]

Step	Current Dish	suffix_sum	total_score	Action
1	5	5	5	Include
2	0	5	10	Include
3	-1	4	14	Include
4	-8	-4	14	Stop

Final answer:

14

The resulting cooking order is:

[-1,0,5]

Score calculation:

(-1*1) + (0*2) + (5*3) = 14

Example 2

Input:

[4,3,2]

After sorting:

[2,3,4]

Step	Current Dish	suffix_sum	total_score
1	4	4	4
2	3	7	11
3	2	9	20

Final answer:

20

Cooking order:

[2,3,4]

Score:

2*1 + 3*2 + 4*3 = 20

Example 3

Input:

[-1,-4,-5]

After sorting:

[-5,-4,-1]

Step	Current Dish	suffix_sum	total_score	Action
1	-1	-1	0	Stop

Final answer:

0

The optimal strategy is to cook nothing.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1)	Only a few variables are used beyond sorting

The main cost comes from sorting the array, which requires O(n log n) time. The subsequent traversal is linear.

The algorithm uses constant auxiliary space because only a few integer variables are maintained. The sort may internally use stack space depending on the language implementation, but no additional data structures proportional to n are created.

Test Cases

from typing import List

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()

        suffix_sum = 0
        total_score = 0
        best_score = 0

        for i in range(len(satisfaction) - 1, -1, -1):
            suffix_sum += satisfaction[i]

            if suffix_sum <= 0:
                break

            total_score += suffix_sum
            best_score = max(best_score, total_score)

        return best_score

sol = Solution()

assert sol.maxSatisfaction([-1, -8, 0, 5, -9]) == 14  # official example 1
assert sol.maxSatisfaction([4, 3, 2]) == 20  # official example 2
assert sol.maxSatisfaction([-1, -4, -5]) == 0  # all negative values
assert sol.maxSatisfaction([0, 0, 0]) == 0  # all zeros
assert sol.maxSatisfaction([1]) == 1  # single positive element
assert sol.maxSatisfaction([-1]) == 0  # single negative element
assert sol.maxSatisfaction([-2, 5]) == 8  # negative still beneficial
assert sol.maxSatisfaction([-1, 0, 1]) == 2  # zero included naturally
assert sol.maxSatisfaction([10, -1, -2]) == 27  # include negatives for shift gain
assert sol.maxSatisfaction([-2, -1, 0, 1, 2]) == 7  # mixed values
assert sol.maxSatisfaction([5, 5, 5]) == 30  # duplicate positives
assert sol.maxSatisfaction([-1000, 1000]) == 1000  # extreme values

Test	Why
[-1,-8,0,5,-9]	Validates official mixed example
[4,3,2]	Validates all positive values
[-1,-4,-5]	Ensures algorithm returns 0 when all values are negative
[0,0,0]	Tests all zero values
[1]	Smallest positive input
[-1]	Smallest negative input
[-2,5]	Confirms negative values can still help
[-1,0,1]	Tests interaction between negative, zero, and positive
[10,-1,-2]	Verifies shifting large positives later is beneficial
[-2,-1,0,1,2]	Tests balanced mixed sequence
[5,5,5]	Tests repeated positive values
[-1000,1000]	Tests extreme constraint values

Edge Cases

One important edge case occurs when all dishes have negative satisfaction values. A naive implementation might still attempt to cook some dishes, producing a negative total score. However, the problem allows discarding all dishes entirely. The greedy solution handles this naturally because the first suffix sum becomes non-positive, causing the algorithm to stop immediately and return 0.

Another subtle case occurs when some negative dishes are still beneficial. For example:

[-2, 5]

Cooking only 5 gives:

5

But cooking [-2, 5] gives:

(-2*1) + (5*2) = 8

This demonstrates why we cannot simply discard all negative values. The implementation correctly includes negative dishes whenever the running suffix sum remains positive.

A third important case involves zeros. Zero-value dishes neither help nor hurt directly, but they can shift positive dishes later in time. The algorithm naturally handles this because zeros preserve the suffix sum without decreasing it. If the running suffix sum stays positive, zeros remain included.

Another edge case is duplicate values. Since the algorithm relies only on sorting and cumulative sums, repeated numbers do not create any special handling issues. Arrays like [5,5,5] are processed correctly and produce the optimal weighted total.

Finally, the smallest possible input size, where n = 1, must also work correctly. The implementation properly handles both positive and negative single-element arrays without requiring any special-case logic.