Watch 8 video solutions for Pizza With 3n Slices, a hard level problem involving Array, Dynamic Programming, Greedy. This walkthrough by CodeHelp - by Babbar has 43,739 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows:
Given an integer array slices that represent the sizes of the pizza slices in a clockwise direction, return the maximum possible sum of slice sizes that you can pick.
Example 1:
Input: slices = [1,2,3,4,5,6] Output: 10 Explanation: Pick pizza slice of size 4, Alice and Bob will pick slices with size 3 and 5 respectively. Then Pick slices with size 6, finally Alice and Bob will pick slice of size 2 and 1 respectively. Total = 4 + 6.
Example 2:
Input: slices = [8,9,8,6,1,1] Output: 16 Explanation: Pick pizza slice of size 8 in each turn. If you pick slice with size 9 your partners will pick slices of size 8.
Constraints:
3 * n == slices.length1 <= slices.length <= 5001 <= slices[i] <= 1000Problem Overview: You are given a circular array where the length is 3n. Each element represents the size of a pizza slice. You must pick exactly n slices such that no two chosen slices are adjacent. Because the pizza is circular, the first and last slices are also adjacent. The goal is to maximize the total size of the chosen slices.
Approach 1: Dynamic Programming - Circular Array (O(n^2) time, O(n^2) space)
The circular constraint means you cannot pick both the first and last slice. Handle this by splitting the problem into two linear cases: include slices [0 ... 3n-2] or include slices [1 ... 3n-1]. Each case becomes a classic non-adjacent selection problem similar to House Robber but with a fixed number of selections. Define dp[i][j] as the maximum sum using the first i slices while selecting j slices. For each slice, either skip it or take it and add its value to dp[i-2][j-1] since adjacent slices cannot be chosen. Compute this for both linear scenarios and return the larger result. The dynamic programming table iterates through slices and selection counts, producing a time complexity of O(n^2) and space complexity of O(n^2). This approach relies heavily on dynamic programming patterns and careful handling of the array boundaries.
Approach 2: Dynamic Programming with Space Optimization (O(n^2) time, O(n) space)
The previous solution stores the entire DP matrix, but each state only depends on earlier rows. You can compress the memory by keeping only the necessary previous states. Instead of maintaining a full dp[i][j] grid, use rolling arrays that track the last two slice states for every possible selection count. While iterating through the slices, update the current values based on the same recurrence: skip the slice or take it and add the value from two steps back. This reduces space from O(n^2) to O(n) while preserving the same transition logic. The algorithm still evaluates both linear ranges to handle the circular structure. This version is preferred when memory constraints matter and demonstrates deeper control over DP state transitions. Although the problem is sometimes associated with greedy intuition, the optimal solution requires structured DP to enforce the exact n selections.
Recommended for interviews: The dynamic programming circular array approach is what most interviewers expect. Explaining why the circular constraint forces two cases shows strong problem decomposition. Implementing the optimized DP version demonstrates mastery of state reduction and memory optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming - Circular Array | O(n^2) | O(n^2) | Best for clarity when first implementing the solution and explaining DP state transitions |
| Dynamic Programming with Space Optimization | O(n^2) | O(n) | Preferred when memory usage matters or when demonstrating advanced DP optimization in interviews |