Problem Description

You have an integer array pizzas of size n, where pizzas[i] represents the weight of the i-th pizza. You must eat exactly 4 pizzas every day until all pizzas are consumed.

When you eat 4 pizzas with weights W, X, Y, and Z (where W ≤ X ≤ Y ≤ Z), you only gain the weight of 1 pizza based on the day:

• On odd-numbered days (days 1, 3, 5, ...), you gain weight Z (the maximum weight among the 4 pizzas)
• On even-numbered days (days 2, 4, 6, ...), you gain weight Y (the second largest weight among the 4 pizzas)

Your goal is to find the maximum total weight you can gain by strategically choosing which 4 pizzas to eat each day.

Constraints:

• n is guaranteed to be a multiple of 4
• Each pizza can only be eaten once
• You must eat all pizzas

For example, if you have 8 pizzas, you'll eat for 2 days (4 pizzas each day). On day 1 (odd), you gain the maximum weight from your chosen 4 pizzas. On day 2 (even), you gain the second largest weight from the remaining 4 pizzas.

The challenge is to determine the optimal grouping of pizzas across all days to maximize your total weight gain.

Intuition

To maximize our total weight gain, we need to think about which pizzas should be the "Z" values (for odd days) and which should be the "Y" values (for even days).

Since we always want to maximize our weight gain, let's consider what happens when we sort all pizzas in ascending order. The key insight is that on odd days we get the maximum weight from 4 pizzas, while on even days we get the second largest weight.

If we have days = n/4 total days, we'll have odd = (days + 1) / 2 odd days and even = days - odd even days.

For odd days, we want the Z values (maximum of each group) to be as large as possible. The best strategy is to take the odd largest pizzas and make each of them the maximum in their respective groups. We pair each of these large pizzas with 3 of the smallest available pizzas. This way, we ensure that the largest pizzas become our Z values.

For even days, we need the Y values (second largest) to be maximized. After using the largest odd pizzas for odd days, we look at the remaining pizzas. Among these, we want to select groups where the second largest value is as high as possible. The optimal approach is to take the next largest available pizzas and make them the second largest in their groups by pairing them strategically.

The greedy approach works here: sort the pizzas, allocate the top odd pizzas for odd days (they'll be the maximum in their groups), then for even days, select pizzas such that the second largest values are maximized. This can be achieved by taking pizzas at positions n - odd - 2, n - odd - 4, etc., making them the Y values in their respective groups.

This strategy ensures we're getting the highest possible weights on both odd and even days.

Learn more about Greedy and Sorting patterns.

Solution Approach

Let's implement the greedy strategy step by step:

Step 1: Sort the pizzas

pizzas.sort()

We sort the array in ascending order to easily identify the largest and smallest pizzas.

Step 2: Calculate the number of days

days = len(pizzas) // 4
odd = (days + 1) // 2
even = days - odd

Since we eat 4 pizzas per day, we have days = n/4 total days. We calculate how many odd days and even days we have.

Step 3: Handle odd days - maximize Z values

ans = sum(pizzas[-odd:])

For odd days, we want the largest pizzas to be the Z (maximum) values. We take the last odd pizzas from the sorted array (these are the largest ones) and sum them up. Each of these will be the maximum in their group of 4 pizzas on odd days.

Step 4: Handle even days - maximize Y values

i = len(pizzas) - odd - 2
for _ in range(even):
    ans += pizzas[i]
    i -= 2

For even days, we need to maximize the Y (second largest) values. After reserving the top odd pizzas for odd days, we start from position n - odd - 2 (skipping the largest unused pizza at n - odd - 1).

The pattern here is clever: by taking every other pizza going backwards (positions n - odd - 2, n - odd - 4, etc.), we ensure these pizzas become the second largest in their groups. This is because:

• The pizza at position n - odd - 1 will be the largest in its group
• The pizza at position n - odd - 2 will be the second largest (our Y value)
• The remaining two pizzas in the group will come from the smaller pizzas

This greedy allocation ensures we maximize the total weight gain by strategically assigning the heaviest available pizzas to be either Z values (on odd days) or Y values (on even days).

Example Walkthrough

Let's walk through an example with 8 pizzas: pizzas = [3, 8, 1, 5, 7, 9, 2, 6]

Step 1: Sort the pizzas After sorting: [1, 2, 3, 5, 6, 7, 8, 9]

Step 2: Calculate days

• Total days = 8 ÷ 4 = 2 days
• Odd days = (2 + 1) ÷ 2 = 1 odd day (day 1)
• Even days = 2 - 1 = 1 even day (day 2)

Step 3: Maximize Z values for odd days We need 1 pizza to be the maximum (Z) on the odd day. Take the largest pizza: 9

• Running total: ans = 9

Step 4: Maximize Y values for even days For the 1 even day, we need to maximize the second-largest (Y) value.

• Start at position: 8 - 1 - 2 = 5 (which is pizza with weight 7)
• Add pizza at index 5: ans = 9 + 7 = 16

Verification of groupings: Let's see how the pizzas would be grouped:

• Day 1 (odd): We eat [1, 2, 3, 9] → gain weight = 9 (maximum)
• Day 2 (even): We eat [5, 6, 7, 8] → gain weight = 7 (second largest)

Total weight gained = 9 + 7 = 16

Notice how the strategy ensures:

• The largest pizza (9) becomes the maximum in a group for the odd day
• The pizza at position 5 (weight 7) becomes the second-largest in its group for the even day
• This greedy allocation maximizes our total weight gain

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array pizzas. This is dominated by the sorting operation pizzas.sort(), which uses a comparison-based sorting algorithm (Timsort in Python) that has O(n × log n) time complexity. The subsequent operations include:

• Calculating days, odd, and even: O(1)
• Slicing to get pizzas[-odd:] and summing: O(odd) which is O(n)
• The for loop that runs even times: O(even) which is O(n)

Since O(n × log n) dominates O(n), the overall time complexity is O(n × log n).

The space complexity is O(log n). Python's Timsort algorithm uses O(log n) auxiliary space for the sorting operation in the worst case due to the merge operations and the stack used for tracking runs. The other variables (days, odd, even, ans, i) use constant space O(1). The slicing operation pizzas[-odd:] creates a new list, but this is used directly in the sum() function and the space can be considered temporary. Therefore, the dominant space complexity comes from the sorting algorithm, resulting in O(log n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Out of Bounds When Computing Even Days

The Pitfall: When calculating the starting index for even days as current_index = len(pizzas) - odd_days - 2, this can become negative if there are too few pizzas or too many odd days. For example, with 4 pizzas (1 day, which is odd), the calculation gives 4 - 1 - 2 = 1, which works. But edge cases might cause issues if not handled properly.

Solution: Add a boundary check or ensure the logic handles the case when even_days = 0:

if even_days > 0:
    current_index = len(pizzas) - odd_days - 2
    for _ in range(even_days):
        max_weight_sum += pizzas[current_index]
        current_index -= 2

2. Misunderstanding the Greedy Assignment Pattern

The Pitfall: Developers might incorrectly assume they should take consecutive pizzas for even days rather than alternating ones. Taking consecutive pizzas (like n-odd-1, n-odd-2, n-odd-3) would result in suboptimal groupings where the second-largest values aren't maximized.

Solution: Ensure the step size is 2 when selecting pizzas for even days. The pattern should be:

• Position n - odd - 2 (becomes Y in its group)
• Position n - odd - 4 (becomes Y in its group)
• And so on...

This ensures each selected pizza can serve as the second-largest in its group of 4.

3. Incorrect Day Count Calculation

The Pitfall: Using integer division incorrectly or confusing the relationship between odd and even days. For instance, writing odd_days = total_days // 2 instead of odd_days = (total_days + 1) // 2 would give wrong results when total_days is odd.

Solution: Use the ceiling division formula correctly:

odd_days = (total_days + 1) // 2
even_days = total_days - odd_days

This ensures that when total_days is odd (e.g., 3), odd_days gets the extra day (2 odd days, 1 even day).

4. Not Sorting the Array

The Pitfall: Forgetting to sort the pizzas array would completely break the greedy algorithm, as the logic depends on accessing the largest elements from the end of a sorted array.

Solution: Always sort the array first:

pizzas.sort()  # Critical - must be sorted for the algorithm to work

5. Off-by-One Error in Loop Iteration

The Pitfall: When iterating for even days, using range(even_days - 1) instead of range(even_days) would miss processing one day's worth of pizzas.

Solution: Ensure the loop runs exactly even_days times:

for _ in range(even_days):  # Correct: iterates exactly even_days times
    max_weight_sum += pizzas[current_index]
    current_index -= 2