Eat Pizzas!
MedPrompt
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!
- On odd-numbered days (1-indexed), you gain a weight of
Z. - On even-numbered days, you gain a weight of
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:
- On day 1, you eat pizzas at indices
[1, 2, 4, 7] = [2, 3, 5, 8]. You gain a weight of 8. - On day 2, you eat pizzas at indices
[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:
- On day 1, you eat pizzas at indices
[4, 5, 6, 0] = [1, 1, 1, 2]. You gain a weight of 2. - On day 2, you eat pizzas at indices
[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] <= 105nis a multiple of 4.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possible ways to partition the n pizzas into n/4 groups of four. For each valid partition, it calculates the total weight gained according to the rules and identifies the maximum possible total weight among all partitions. This is a brute-force method that guarantees finding the optimal solution by checking every possibility.
Algorithm
- Define a recursive function
findMaxWeight(available_pizzas, day). - Base Case: If
available_pizzasis empty, return 0. - Recursive Step:
- Initialize
max_gain = 0. - Iterate through every possible combination
Cof 4 pizzas fromavailable_pizzas. - For each combination
C:- Determine the
remaining_pizzas. - Sort
Cto find the weightsW, X, Y, Z. - Calculate
current_gain:Zifdayis odd,Yifdayis even. - Recursively call
findMaxWeight(remaining_pizzas, day + 1). - Update
max_gainwith the maximum total gain found.
- Determine the
- Initialize
- Return
max_gain. - The initial call is
findMaxWeight(initial_pizzas, 1).
Walkthrough
The core of this method is a recursive function that builds a valid partition day by day. Let's say we have a function solve(pizzas, day), where pizzas is the list of currently available pizzas and day is the current day number (1-indexed).
The base case for the recursion is when the list of pizzas becomes empty, which means we have successfully grouped all pizzas. In this case, the gain is 0.
In the recursive step, the function tries to form a group of 4 for the current day. It iterates through all unique combinations of 4 pizzas from the pizzas list. For each combination, it calculates the weight it would gain for that day. If day is odd, the gain is the maximum weight in the combination. If day is even, the gain is the second-largest weight. This gain is added to the result of a recursive call made with the remaining pizzas and the next day (day + 1). The function keeps track of the maximum total gain found across all possible combinations for the current day.
While this method is straightforward in concept, its computational cost is enormous. The number of ways to partition n items into n/4 groups of 4 grows factorially, making this solution infeasible for anything but very small values of n.
Complexity
Time
O(n!) - The number of ways to partition `n` pizzas into `n/4` groups of 4 is given by `n! / ((4!)^(n/4) * (n/4)!)`, which is a combinatorial explosion. This exponential complexity makes the approach too slow for the given constraints.
Space
O(n) - The space is primarily used by the recursion stack. The depth of the recursion is `n/4`, and at each level, we might store a list of remaining pizzas, leading to `O(n^2)` in a naive implementation, but can be optimized to `O(n)` by passing indices or modifying a single list.
Trade-offs
Pros
Guaranteed to find the absolute maximum weight.
Serves as a good baseline for understanding the problem's complexity.
Cons
Extremely high time complexity, making it impractical for the given constraints.
Complex to implement correctly due to the combination generation.
A more optimized approach than brute force is to use dynamic programming. By sorting the pizzas first, we can attempt to solve the problem on contiguous subarrays of pizzas. We can define a recursive relation with memoization to compute the maximum weight for a subproblem, which is defined by the range of pizzas currently under consideration.
Algorithm
- First, sort the
pizzasarray in ascending order. - Define a recursive function
solve(l, r)with memoization, wherelandrare the start and end indices of the current subarray of pizzas. - The number of groups already formed is
k = (n - (r-l+1)) / 4. The current day isk + 1. - Base Case: If
l > r, return 0. - Recursive Step: Based on whether the current day is odd or even, calculate the gain from three possible groupings of pizzas from the boundaries:
- Group of 4 smallest:
{p_l, p_{l+1}, p_{l+2}, p_{l+3}}. Recurse onsolve(l+4, r). - Group of 2 smallest and 2 largest:
{p_l, p_{l+1}, p_{r-1}, p_r}. Recurse onsolve(l+2, r-2). - Group of 4 largest:
{p_{r-3}, p_{r-2}, p_{r-1}, p_r}. Recurse onsolve(l, r-4).
- Group of 4 smallest:
- The value of
solve(l, r)is the maximum of the total gains from these three choices. - Store the result in a 2D memoization table
memo[l][r]to avoid recomputing.
Walkthrough
After sorting the pizzas array, we can define a function dp(l, r) representing the maximum weight obtainable from the pizzas in the index range [l, r]. The number of pizzas in this range, r-l+1, must be a multiple of 4.
The key idea is to decide which group of 4 to form from the available pizzas. A common DP strategy for such problems is to assume that the next group to be formed will consist of pizzas from the ends of the sorted subarray. This gives us a few choices:
- Take the four smallest pizzas:
pizzas[l]topizzas[l+3]. - Take the two smallest and two largest:
pizzas[l],pizzas[l+1],pizzas[r-1],pizzas[r]. - Take the four largest pizzas:
pizzas[r-3]topizzas[r].
The day number (odd or even) can be calculated based on how many pizzas have been consumed so far (i.e., those outside the [l, r] range). Based on the day, we calculate the gain for each of the three choices and add it to the result of the recursive call on the remaining subarray. For example, for choice 1, we would recurse on dp(l+4, r). The final result for dp(l, r) is the maximum of these three options.
We use a 2D array for memoization to store the results of dp(l, r), which reduces the complexity from exponential to polynomial. However, O(n^2) is still too slow for the problem's constraints.
Complexity
Time
O(n^2) - There are `O(n^2)` possible states `(l, r)`, and each state takes constant time to compute assuming subproblems are memoized.
Space
O(n^2) - A 2D array of size `n x n` is required for the memoization table.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Introduces a structured way of thinking about subproblems.
Cons
The time and space complexity of
O(n^2)is too high for the given constraints.The underlying assumption that the optimal group choice always involves pizzas from the boundaries of the remaining sorted array might be incorrect, so this DP formulation may not yield the correct optimal answer for all cases.
The most efficient and optimal solution is a greedy algorithm. The main insight is that to maximize the total weight, we should always use the largest available pizzas for the roles that contribute to the score. On odd days, this is the largest pizza (Z), and on even days, it's the second-largest (Y). By sorting the pizzas, we can systematically pick the best pizzas for these roles.
Algorithm
- Sort the
pizzasarray in ascending order. - Calculate the total number of days,
D = n / 4. - Initialize
total_weight = 0. - Initialize a pointer
right = n - 1to track the largest available pizza. - Calculate gain from odd days: There are
(D + 1) / 2odd days. For each, we gain the weight of the largest pizza (Z). We take the(D + 1) / 2largest pizzas from the array. Loop this many times, addingpizzas[right]tototal_weightand decrementingrighteach time. - Calculate gain from even days: There are
D / 2even days. For each, we gain the weight of the second-largest pizza (Y). This requires taking two large pizzas (YandZ). We take the next2 * (D / 2)largest pizzas. LoopD / 2times. In each iteration, decrementrightonce (to skip theZpizza for the group) and then addpizzas[right]tototal_weight(theYpizza). Then decrementrightagain. - Return
total_weight.
Walkthrough
This approach is based on a greedy strategy that becomes clear after sorting the pizzas array. Let the sorted weights be p_0, p_1, ..., p_{n-1}.
The total gain is the sum of Z's from odd days and Y's from even days. To maximize this sum, we should assign the largest possible values to these contributing pizza slots.
-
Odd Days: There are
(n/4 + 1) / 2odd-numbered days. On these days, we gain the weight of the largest pizza (Z) in the group. To maximize our score, we should use the absolute largest pizzas in the entire collection for this purpose. Therefore, we assign the(n/4 + 1) / 2largest pizzas (p_{n-1}, p_{n-2}, ...) to be theZ's on these odd days. -
Even Days: There are
(n/4) / 2even-numbered days. On these days, we gain the weight of the second-largest pizza (Y). To get a highYvalue, the group must contain two large pizzas, which will becomeYandZ. To maximize the sum ofY's, we should use the next set of largest available pizzas. For each of the(n/4) / 2even days, we form a pair from the largest remaining pizzas. The larger of the pair becomesZ(and doesn't contribute to the score), and the smaller becomesY(and contributes to the score).
The remaining smallest pizzas are used to fill the rest of the spots in the groups. Since their weights don't contribute to the score, their specific assignment doesn't matter.
This logic leads to a simple and efficient implementation:
import java.util.Arrays; class Solution { public long eatPizzas(int[] pizzas) { Arrays.sort(pizzas); int n = pizzas.length; int days = n / 4; long totalWeight = 0; int right = n - 1; // Pizzas for Z on odd days int oddDays = (days + 1) / 2; for (int i = 0; i < oddDays; i++) { totalWeight += pizzas[right]; right--; } // Pizzas for Y on even days int evenDays = days / 2; for (int i = 0; i < evenDays; i++) { // For an even day, we need two large pizzas to be Z and Y. // pizzas[right] would be Z, and pizzas[right-1] would be Y. // We gain the weight of Y. right--; // This pizza is Z for the group, no gain totalWeight += pizzas[right]; // This pizza is Y, gain its weight right--; } return totalWeight; }}Complexity
Time
O(n log n) - The dominant operation is sorting the `pizzas` array. The subsequent loops to calculate the total weight run in `O(n/4)`, which is linear. Thus, the total time complexity is `O(n log n)`.
Space
O(log n) or O(n) - This depends on the implementation of the sorting algorithm. An in-place sort like Heapsort uses `O(log n)` space for recursion, while TimSort (used in Java for objects) or MergeSort can use up to `O(n)` space.
Trade-offs
Pros
Optimal and correct for all cases.
Highly efficient with a time complexity dominated by sorting.
Simple and clean to implement.
Cons
The correctness of the greedy strategy is not immediately obvious and requires a careful proof or strong intuition.
Solutions
Solution
class Solution {public long maxWeight(int[] pizzas) { int n = pizzas.length; int days = n / 4; Arrays.sort(pizzas); int odd = (days + 1) / 2; int even = days / 2; long ans = 0; for (int i = n - odd; i < n; ++i) { ans += pizzas[i]; } for (int i = n - odd - 2; even > 0; --even) { ans += pizzas[i]; i -= 2; } return ans; }}class Solution {public: long long maxWeight(vector<int> &pizzas) { int n = pizzas.size(); int days = pizzas.size() / 4; ranges ::sort(pizzas); int odd = (days + 1) / 2; int even = days - odd; long long ans = accumulate(pizzas.begin() + n - odd, pizzas.end(), 0LL); for (int i = n - odd - 2; even; --even) { ans += pizzas[i]; i -= 2; } return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.