Problem 1402

Abstract / Summary

Given a list of dish piles, repeatedly combine the two smallest piles until one pile remains and return its size.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
14 lines | 365 bytes | submitted October 3, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 77% (200k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Dynamic Programming
  • Greedy
  • Sorting
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 5 | μ = 5.04 | σ = 1.65

Complexity Analysis

Time: polynomial
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
28 links | 17 authors | 6 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

6 easy 4 medium 3 hard
14 solutions   October 3, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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