Python 1402.py
class Solution:
def maxSatisfaction(self, satisfaction: List[int]) -> int:
satisfaction.sort()
best = 0
while satisfaction:
total = 0
for i, s in enumerate(satisfaction):
total += (i + 1) * s
best = max(best, total)
del satisfaction[0]
return best
Difficulty
and has an acceptance rate of about 77% (200k+ submissions).
Typical patterns to solve this problem:
- Array
- Dynamic Programming
- Greedy
- Sorting
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided Solution class implements a method maxSatisfaction that receives a list of integers representing satisfaction levels for dishes. The goal of the method is to determine the maximum possible “like-time” coefficient that can be achieved by arranging the dishes in an optimal order and possibly discarding some of them. The algorithm proceeds by first sorting the input, then iteratively evaluating the total coefficient for the current list, recording the best value seen, and finally removing the smallest element before the next iteration. The final result is the highest coefficient encountered during this process.
Key Steps
Sorting the Input
satisfaction.sort()
Sorting arranges the satisfaction values in non-decreasing order. This ordering places the most negative values at the beginning of the list, which simplifies the later step of discarding low-value dishes. By having the list sorted, the algorithm can systematically eliminate the least beneficial elements while preserving the relative order of the remaining items.
Computing the Current Total
total = 0
for i, s in enumerate(satisfaction):
total += (i + 1) * s
For each iteration, the method computes the “like-time” coefficient for the current list. The index i (zero-based) is incremented by one to reflect the cooking time of each dish, and the product (i + 1) * s contributes to the cumulative total. This loop captures the effect of both the satisfaction value and its position in the cooking sequence.
Updating the Best Result
best = max(best, total)
After calculating the total for the current arrangement, the algorithm compares it with the best value recorded so far. If the new total exceeds the previous best, best is updated accordingly. This ensures that the method retains the maximum coefficient observed across all examined suffixes of the sorted list.
Discarding the Least Beneficial Dish
del satisfaction[0]
The first element of the sorted list-being the smallest satisfaction value-is removed before the next iteration. By deleting this element, the algorithm effectively explores the scenario where the least beneficial dish is omitted from the cooking order. Repeating this removal step generates all possible suffixes of the sorted list, each representing a different subset of dishes to be prepared.
Returning the Result
return best
When the while-loop terminates (i.e., the list becomes empty), the method returns the highest coefficient stored in best. This value represents the optimal total achievable by selecting an appropriate subset of dishes and ordering them according to the cooking time rule.
Edge Cases Handled
When the input list is empty, the initial best value of 0 remains unchanged, and the method returns 0. This correctly reflects that no dishes can be cooked, yielding a zero coefficient.
If all satisfaction values are negative, the sorting step places the most negative numbers at the front. The iterative removal of the first element gradually eliminates these detrimental values. Eventually, the loop may reach a state where the list is empty, and the best coefficient stays at 0, indicating that the optimal strategy is to cook nothing.
When the list contains a mixture of negative and positive values, the algorithm discards negative entries one by one, evaluating the total after each removal. This process naturally discovers the point at which the remaining positive values outweigh the cost of including any remaining negatives, thereby capturing the optimal subset.
For a list consisting solely of positive values, the first iteration (with the full sorted list) already yields the maximum possible coefficient, because removing any positive element would only reduce the total. The best variable captures this maximum on the first pass, and subsequent iterations produce lower totals, leaving best unchanged.
Performance Optimizations Observed
The initial sorting operation organizes the data so that the least beneficial dishes are positioned at the front, enabling a simple deletion strategy that avoids more complex selection logic. By repeatedly deleting the first element, the algorithm reduces the size of the list in each iteration, which naturally decreases the amount of work performed by the inner loop that computes the total. This progressive shrinking of the list means that later iterations require fewer arithmetic operations than earlier ones.
The use of the built-in max function to update the best result provides a concise and efficient comparison without the need for additional conditional branching. Additionally, the direct manipulation of the list with del satisfaction[0] avoids creating new list objects, thereby limiting memory overhead during the iterative process.
Overall, the combination of sorting, incremental list reduction, and in-place updates contributes to a streamlined execution flow that leverages Python’s native operations for speed and memory efficiency.
ELI5 - Simplified Explanation
Imagine you have a big bag of mixed snacks, and each snack has a number on it that shows how much you like it. Some snacks have big numbers because they are very yummy, and some have small or even negative numbers because they taste like broccoli.
First, the code lines up all the snacks from the least favorite to the most favorite. This makes it easy to see which ones are the best.
Next, the code starts a game to find the perfect way to eat them. It takes the whole line of snacks and adds up a score. To get the score, it gives the first snack one point, the second snack two points, and so on, multiplying those points by how much you like the snack. This means you want the yummy snacks to be later in the line so they get multiplied by a bigger number.
After calculating the score, the code takes away the snack that was at the very front of the line because that one often makes the final score smaller instead of bigger. It keeps doing this, checking the score every time it removes a snack, until there are no snacks left. Throughout the whole game, the code remembers the highest score it ever saw and keeps that as the winner.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||
|---|---|---|---|---|---|---|---|
| author | solutions | ||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||
| WalkCCC | C++ | Java | Python | ||||
| leetcode.ca | C++ | Java | Python | Go | TS | ||
| Progiez | C++ | Java | Python | ||||
| github | black-shadows | C++ | |||||
| charles-wangkai | Java | ||||||
| everthis | JS | ||||||
| fpdjsns | C++ | ||||||
| fsq | C++ | ||||||
| gouthampradhan | Java | ||||||
| JoshCrozier | JS | ||||||
| keineahnung2345 | C++ | ||||||
| lkwq007 | Python | ||||||
| lzl124631x | C++ | ||||||
| varunu28 | Java | ||||||
| vthwang | Java | ||||||
| wisdompeak | C++ | ||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||
| WalkCCC | C++, Python, Java | ||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | ||||||
| Progiez | C++, Java, Python | ||||||
| black-shadows | C++, C++ | ||||||
| charles-wangkai | Java | ||||||
| everthis | JavaScript | ||||||
| fpdjsns | C++ | ||||||
| fsq | C++ | ||||||
| gouthampradhan | Java | ||||||
| JoshCrozier | JavaScript | ||||||
| keineahnung2345 | C++ | ||||||
| lkwq007 | Python | ||||||
| lzl124631x | C++ | ||||||
| varunu28 | Java | ||||||
| vthwang | Java | ||||||
| wisdompeak | C++ |
Videos
Solved On The Same Day
- problem 598: Range Addition II
- problem 653: Two Sum IV - Input is a BST
- problem 1470: Shuffle the Array
- problem 1512: Number of Good Pairs
- problem 1920: Build Array from Permutation
- problem 1929: Concatenation of Array
- problem 396: Rotate Function
- problem 877: Stone Game
- problem 1033: Moving Stones Until Consecutive
- problem 2396: Strictly Palindromic Number
- problem 1406: Stone Game III
- problem 1463: Cherry Pickup II
- problem 1510: Stone Game IV
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality