# Eat Pizzas!
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/eat-pizzas)
Canonical: https://scaleengineer.com/dsa/problems/eat-pizzas!
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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 * 105`
* `1 <= pizzas[i] <= 105`
* `n` is a multiple of 4.

# Approaches
## Brute Force with Backtracking
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.
**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.
**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.
### Explanation
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`.
### Algorithm
- Define a recursive function `findMaxWeight(available_pizzas, day)`.
- **Base Case:** If `available_pizzas` is empty, return 0.
- **Recursive Step:**
  - Initialize `max_gain = 0`.
  - Iterate through every possible combination `C` of 4 pizzas from `available_pizzas`.
  - For each combination `C`:
    - Determine the `remaining_pizzas`.
    - Sort `C` to find the weights `W, X, Y, Z`.
    - Calculate `current_gain`: `Z` if `day` is odd, `Y` if `day` is even.
    - Recursively call `findMaxWeight(remaining_pizzas, day + 1)`.
    - Update `max_gain` with the maximum total gain found.
- Return `max_gain`.
- The initial call is `findMaxWeight(initial_pizzas, 1)`.

## Dynamic Programming on Subproblems
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.
**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.
**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.
### Explanation
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:
1.  Take the four smallest pizzas: `pizzas[l]` to `pizzas[l+3]`. 
2.  Take the two smallest and two largest: `pizzas[l]`, `pizzas[l+1]`, `pizzas[r-1]`, `pizzas[r]`.
3.  Take the four largest pizzas: `pizzas[r-3]` to `pizzas[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.
### Algorithm
- First, sort the `pizzas` array in ascending order.
- Define a recursive function `solve(l, r)` with memoization, where `l` and `r` are 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 is `k + 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:
  1.  Group of 4 smallest: `{p_l, p_{l+1}, p_{l+2}, p_{l+3}}`. Recurse on `solve(l+4, r)`.
  2.  Group of 2 smallest and 2 largest: `{p_l, p_{l+1}, p_{r-1}, p_r}`. Recurse on `solve(l+2, r-2)`.
  3.  Group of 4 largest: `{p_{r-3}, p_{r-2}, p_{r-1}, p_r}`. Recurse on `solve(l, r-4)`.
- 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.

## Optimal Greedy Approach with Sorting
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.
**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.
**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.
### Explanation
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) / 2` odd-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) / 2` largest pizzas (`p_{n-1}, p_{n-2}, ...`) to be the `Z`'s on these odd days.

- **Even Days:** There are `(n/4) / 2` even-numbered days. On these days, we gain the weight of the second-largest pizza (`Y`). To get a high `Y` value, the group must contain two large pizzas, which will become `Y` and `Z`. To maximize the sum of `Y`'s, we should use the next set of largest available pizzas. For each of the `(n/4) / 2` even days, we form a pair from the largest remaining pizzas. The larger of the pair becomes `Z` (and doesn't contribute to the score), and the smaller becomes `Y` (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:
```java
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;
    }
}
```
### Algorithm
1. Sort the `pizzas` array in ascending order.
2. Calculate the total number of days, `D = n / 4`.
3. Initialize `total_weight = 0`.
4. Initialize a pointer `right = n - 1` to track the largest available pizza.
5. **Calculate gain from odd days:** There are `(D + 1) / 2` odd days. For each, we gain the weight of the largest pizza (`Z`). We take the `(D + 1) / 2` largest pizzas from the array. Loop this many times, adding `pizzas[right]` to `total_weight` and decrementing `right` each time.
6. **Calculate gain from even days:** There are `D / 2` even days. For each, we gain the weight of the second-largest pizza (`Y`). This requires taking two large pizzas (`Y` and `Z`). We take the next `2 * (D / 2)` largest pizzas. Loop `D / 2` times. In each iteration, decrement `right` once (to skip the `Z` pizza for the group) and then add `pizzas[right]` to `total_weight` (the `Y` pizza). Then decrement `right` again.
7. Return `total_weight`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```