Watch 8 video solutions for Eat Pizzas!, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Aryan Mittal has 2,158 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array pizzas of size n, where pizzas[i] represents the weight of the ith pizza. Every day, you eat exactly 4 pizzas. Due to your incredible metabolism, when you eat pizzas of weights W, X, Y, and Z, where W <= X <= Y <= Z, you gain the weight of only 1 pizza!
Z.Y.Find the maximum total weight you can gain by eating all pizzas optimally.
Note: It is guaranteed that n is a multiple of 4, and each pizza can be eaten only once.
Example 1:
Input: pizzas = [1,2,3,4,5,6,7,8]
Output: 14
Explanation:
[1, 2, 4, 7] = [2, 3, 5, 8]. You gain a weight of 8.[0, 3, 5, 6] = [1, 4, 6, 7]. You gain a weight of 6.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
Explanation:
[4, 5, 6, 0] = [1, 1, 1, 2]. You gain a weight of 2.[1, 2, 3, 7] = [1, 1, 1, 1]. You gain a weight of 1.The total weight gained after eating all the pizzas is 2 + 1 = 3.
Constraints:
4 <= n == pizzas.length <= 2 * 1051 <= pizzas[i] <= 105n is a multiple of 4.Problem Overview: You are given an array representing pizza sizes. Each day you eat pizzas following specific rules that determine which pizza contributes to your total weight gain. The goal is to maximize the total weight you gain by choosing pizzas in an optimal order.
Approach 1: Brute Force Simulation (Exponential Time, O(n!) time, O(n) space)
The most direct idea is to try every possible order of eating pizzas and compute the resulting weight gain. For each permutation, simulate the eating rules day by day and track the total gained weight. This guarantees the correct answer because it explores every possible arrangement. However, the number of permutations grows factorially, making this approach impractical even for moderate input sizes. It mainly helps understand how the daily selection rules affect which pizzas should be prioritized.
Approach 2: Greedy + Sorting (Optimal, O(n log n) time, O(1) extra space)
The key observation is that only certain pizzas in each group actually contribute to the score. After sorting the array, you can greedily assign the largest pizzas to the days where they maximize the gain. Sorting lets you reason about the order of sizes and consistently choose the best available pizza for each scoring position. Using two pointers or index tracking from the end of the sorted array, you simulate the daily selection rules and skip pizzas that don't contribute to the score.
This greedy strategy works because larger pizzas should always be reserved for the positions that count toward the total gain. Once the array is sorted, every decision becomes locally optimal and does not hurt future choices. The algorithm mainly performs a sort followed by a linear pass to simulate the eating process.
The approach relies on ordering from sorting and making locally optimal choices using a greedy strategy while iterating through the array. Time complexity is O(n log n) due to sorting, and space complexity stays O(1) if sorting is done in place.
Recommended for interviews: The greedy + sorting solution is what interviewers expect. A brief mention of brute force demonstrates understanding of the problem constraints, but the sorted greedy simulation shows the real insight: only specific pizzas affect the score, so you should reserve the largest ones for those positions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(n!) | O(n) | Conceptual baseline to understand how ordering affects total gain |
| Greedy + Sorting | O(n log n) | O(1) | Optimal solution when pizza sizes can be reordered freely |