#3457

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Eat Pizzas!

Maximize the total weight gained by optimally eating pizzas in groups of four using greedy selection and invariant validation.

array greedy sorting

Problem Statement

You are given an array pizzas of length n, where pizzas[i] represents the weight of the ith pizza. Each day, you must eat exactly four pizzas. For a group of pizzas with weights W <= X <= Y <= Z, your gain is equal to the second-largest pizza's weight Y.

Your task is to compute the maximum total weight gained by consuming all pizzas optimally. It is guaranteed that n is a multiple of four and each pizza can be eaten exactly once. Use a greedy strategy to maximize daily gains while respecting the invariant rule of choosing four pizzas per day.

Examples

Example 1

Input: pizzas = [1,2,3,4,5,6,7,8]

Output: 14

The total weight gained after eating all the pizzas is 8 + 6 = 14 .

Example 2

Input: pizzas = [2,1,1,1,1,1,1,1]

Output: 3

The total weight gained after eating all the pizzas is 2 + 1 = 3.

Constraints

4 <= n == pizzas.length <= 2 * 105
1 <= pizzas[i] <= 105
n is a multiple of 4.

Solution Approach

Sort the Array

Begin by sorting the pizzas array in ascending order. Sorting ensures that we can consistently select the smallest and largest pizzas efficiently for each day.

Apply Greedy Pairing

For each day, pick the largest remaining pizza and the three smallest remaining pizzas. Add the second-largest pizza in this selection to the total gain. Remove these four pizzas from the array and repeat until all pizzas are eaten.

Iterate Until Completion

Continue the process until the array is empty. The invariant rule that your gain is the second-largest pizza ensures that pairing the largest with the smallest three each day maximizes the total weight over all days.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n). Each day requires O(1) operations to pick four pizzas and update the total, repeated n/4 times, resulting in overall O(n log n) time and O(1) extra space besides the input.

What Interviewers Usually Probe

Candidate starts by sorting pizzas and reasoning about daily selections.
Candidate identifies the invariant that gain is the second-largest pizza per day.
Candidate efficiently removes selected pizzas and calculates running total gain.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort the array, leading to suboptimal pairing and total gain.
Incorrectly selecting the pizza to add to the gain (must be the second-largest in each group).
Not updating or removing pizzas properly after each day's selection, causing array misalignment.

Follow-up variants

Change the group size from four to another number with a similar invariant rule.
Maximize total weight when gain is defined as the sum of the two largest pizzas per day.
Introduce multiple days with alternating rules for which pizza contributes to gain.

FAQ

What is the main strategy for Eat Pizzas! problem?

The main strategy is to sort pizzas and use a greedy selection pairing the largest pizza with the three smallest remaining to maximize daily gain.

Why do we pick the second-largest pizza each day?

Because the problem defines that your weight gain from a group of four pizzas is the second-largest pizza's weight, enforcing the invariant rule.

Can this approach handle large n efficiently?

Yes, sorting takes O(n log n) and each day's selection is constant time, so the overall time complexity is O(n log n), suitable for large n.

What mistakes should I avoid with this greedy pattern?

Avoid not sorting, misidentifying the second-largest pizza, or failing to remove used pizzas from the array.

Are there variations of Eat Pizzas! using this greedy plus invariant pattern?

Yes, you can vary the group size or the rule for which pizza contributes to gain, but the greedy invariant approach still applies.

terminal

Solution

Solution 1: Greedy + Sorting

According to the problem description, we can eat $4$ pizzas each day. On odd days, we get the maximum value among these $4$ pizzas, and on even days, we get the second largest value among these $4$ pizzas.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxWeight(self, pizzas: List[int]) -> int:
        days = len(pizzas) // 4
        pizzas.sort()
        odd = (days + 1) // 2
        even = days - odd
        ans = sum(pizzas[-odd:])
        i = len(pizzas) - odd - 2
        for _ in range(even):
            ans += pizzas[i]
            i -= 2
        return ans

Continue Practicing

#3462 maximum sum with at most k elements #3424 minimum cost to make arrays identical #3413 maximum coins from k consecutive bags