LeetCode 3457 - Eat Pizzas!

The problem presents an array pizzas of size n where each element represents the weight of a pizza. Every day, you must eat exactly 4 pizzas, and the total weight you gain from these 4 pizzas depends on whether the day is odd or even.

leetcodemediumarraygreedysorting

LeetCode Problem 3457

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem presents an array pizzas of size n where each element represents the weight of a pizza. Every day, you must eat exactly 4 pizzas, and the total weight you gain from these 4 pizzas depends on whether the day is odd or even. On odd-numbered days, your weight gain is equal to the heaviest pizza eaten that day, and on even-numbered days, it is equal to the second heaviest pizza. The goal is to consume all pizzas in a way that maximizes your total weight gain.

The constraints ensure that n is always a multiple of 4, which simplifies day partitioning, and pizzas[i] can be large, up to 100,000. The array can be as large as 200,000 elements, meaning any solution with higher than O(n log n) complexity could be too slow. The problem guarantees that every pizza is eaten exactly once, so there is no partial consumption or leftover to worry about.

Edge cases include arrays where all pizzas are the same weight, arrays where the largest pizzas should ideally be eaten on odd days to maximize gain, or arrays with minimum weight values.

Approaches

A brute-force approach would attempt every possible grouping of 4 pizzas per day and calculate the total gain for each permutation. This approach is correct but infeasible for large n because the number of permutations is enormous, approximately (n!) / ((4!)^(n/4)), which is far beyond acceptable computational limits.

The key observation for an optimal solution is that to maximize gain, we should sort the pizzas in ascending order and always consume pizzas from largest to smallest in blocks of four. This ensures that on odd days, we get the largest pizza possible, and on even days, the second-largest pizza of the remaining group, which aligns with the gain rules. By consuming from the end of the sorted list and skipping the smallest pizza in each group, we maximize weight gain efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O((n!) / (4!)^(n/4)) O(n) Check all permutations of pizza consumption to maximize gain
Optimal O(n log n) O(1) or O(n) Sort pizzas and greedily select groups from largest to smallest

Algorithm Walkthrough

  1. Sort the pizzas array in ascending order. Sorting ensures that we can easily pick the largest pizzas to maximize gain according to the day's rules.

  2. Initialize a variable total_weight to accumulate the total weight gain.

  3. Use two pointers: one starting at the end of the array (right) to pick the largest pizzas, and another at the beginning (left) for the smallest ones to skip.

  4. For each group of 4 pizzas (loop until all pizzas are consumed):

  5. On odd-numbered days, select the largest remaining pizza as the gain.

  6. On even-numbered days, select the second largest remaining pizza as the gain.

  7. Always remove the two largest pizzas and the smallest pizza from consideration; they correspond to the day's consumption rules.

  8. Continue until all pizzas are grouped and eaten.

  9. Return total_weight as the maximum total weight gain.

Why it works: By always consuming the largest remaining pizzas, we ensure that the weight gain for each day is maximized. The invariant is that after picking 4 pizzas per day, we reduce the problem size by 4 while guaranteeing optimal gain by choosing from the largest end. Sorting and the greedy selection guarantee correctness because choosing smaller pizzas in place of larger ones would never improve the total.

Python Solution

from typing import List

class Solution:
    def maxWeight(self, pizzas: List[int]) -> int:
        pizzas.sort()
        total_weight = 0
        left, right = 0, len(pizzas) - 1
        day = 1
        
        while left < right:
            if day % 2 == 1:
                total_weight += pizzas[right]  # gain from largest pizza
            else:
                total_weight += pizzas[right - 1]  # gain from second largest pizza
            # remove the largest two pizzas and the smallest one
            right -= 2
            left += 1
            day += 1
        
        return total_weight

In the Python code, we first sort the pizzas, then use a two-pointer approach. right points to the largest pizza, left points to the smallest pizza. For each day, we accumulate weight according to the rules and adjust pointers to remove consumed pizzas.

Go Solution

import "sort"

func maxWeight(pizzas []int) int64 {
    sort.Ints(pizzas)
    var totalWeight int64
    left, right := 0, len(pizzas)-1
    day := 1
    
    for left < right {
        if day%2 == 1 {
            totalWeight += int64(pizzas[right])
        } else {
            totalWeight += int64(pizzas[right-1])
        }
        right -= 2
        left += 1
        day += 1
    }
    
    return totalWeight
}

The Go implementation mirrors Python. We use int64 for totalWeight to avoid integer overflow, which is important as pizzas[i] can be large. Sorting and two-pointer traversal are identical.

Worked Examples

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

After sorting: [1,2,3,4,5,6,7,8]

Day Pizzas chosen Gain Pointers update
1 (odd) [8,7,2,1] 8 left=1, right=6
2 (even) [6,5,3,4] 6 left=2, right=4

Total weight = 8 + 6 = 14

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

After sorting: [1,1,1,1,1,1,1,2]

Day Pizzas chosen Gain Pointers update
1 (odd) [2,1,1,1] 2 left=1, right=6
2 (even) [1,1,1,1] 1 left=2, right=4

Total weight = 2 + 1 = 3

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates; iterating through pizzas is O(n)
Space O(1) Two pointers and variables; sort can be in-place

Sorting ensures we can greedily pick the optimal pizzas per day efficiently.

Test Cases

# Basic examples
assert Solution().maxWeight([1,2,3,4,5,6,7,8]) == 14  # problem example
assert Solution().maxWeight([2,1,1,1,1,1,1,1]) == 3  # problem example

# Edge cases
assert Solution().maxWeight([1,1,1,1]) == 1  # minimum n, all equal
assert Solution().maxWeight([5,5,5,5]) == 5  # minimum n, all equal large
assert Solution().maxWeight([1,2,3,4,5,6,7,8,9,10,11,12]) == 26  # larger n, sequential
assert Solution().maxWeight([10**5]*8) == 2*10**5  # maximum pizza weights
Test Why
[1,2,3,4,5,6,7,8] Basic problem example
[2,1,1,1,1,1,1,1] Gains vary based on largest pizza choice
[1,1,1,1] Minimum size, all equal
[5,5,5,5] Minimum size, large values
[1..12] Multiple days, sequential values
[10**5]*8 Maximum weight values, tests int handling

Edge Cases

One edge case is when all pizzas have the same weight. This could lead to confusion about which pizza is considered the largest or second-largest. The implementation handles this naturally because sorting maintains order, and gain selection uses fixed indices.

Another edge case is the minimum number of pizzas (4). The algorithm correctly handles a single day, whether odd or even, since the pointers left and right still correctly select the largest and second-largest pizza.

Finally, an array with very large weights could cause integer overflow if the total weight is stored in a 32-bit integer. In Python, integers are arbitrary precision, so there is no issue. In Go, using int64 ensures safety.