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.
This approach utilizes dynamic programming to solve the problem of selecting non-consecutive maximum slices. Since the pizza is circular, we consider two possible scenarios: including the first slice and excluding the last one, and excluding the first slice and including the last one. We solve both scenarios using a dynamic programming table to store the maximum sum for slices that can be picked.
This C solution defines a helper function solve that uses dynamic programming to calculate the maximum sum for picking non-consecutive slices. The main function maxSizeSlices calls solve for two scenarios to handle the circular nature of the problem, ensuring that slices are not picked consecutively across the cycle.
Time Complexity: O(n^2), where n is the number of slices. Space Complexity: O(n^2) for the DP table.
This approach focuses on optimizing the space used in dynamic programming by maintaining just two previous states rather than a whole table. This can significantly reduce the space complexity from O(n^2) to O(n), improving the practicality of the solution when dealing with larger inputs.
This C solution maintains only two arrays to store results from prior iterations of dynamic programming calculations, effectively reducing space complexity while maintaining the correct logic for slice selection.
Time Complexity: O(n^2), Space Complexity: O(n), where n is the number of slices.
We can transform this problem into: In a circular array of length 3n, select n non-adjacent numbers so that the sum of these n numbers is maximized.
The proof is as follows:
n = 1, we can choose any number in the array.n > 1, there must exist a number such that there are two consecutive numbers on one side of it that have not been selected, and at least one number on the other side has not been selected. Therefore, we can remove this number and the numbers on both sides of it from the array, and then the remaining 3(n - 1) numbers form a new circular array. The problem scale is reduced to selecting n - 1 non-adjacent numbers in a circular array of length 3(n - 1), so that the sum of these n - 1 numbers is maximized.Therefore, the problem we need to solve can be transformed into: In a circular array of length 3n, select n non-adjacent numbers so that the sum of these n numbers is maximized.
In a circular array, if the first number is selected, the last number cannot be selected. If the last number is selected, the first number cannot be selected. Therefore, we can split the circular array into two arrays, one is without the first number, and the other is without the last number. Then solve the maximum value of these two arrays separately, and finally take the larger of the two maximum values.
We use a function g(nums), which represents the maximum sum of selecting n non-adjacent numbers in the array nums. Then our goal is to find the larger value between g(slices) and g(slices[1:]).
The solution method of function g(nums) is as follows:
We denote the length of array nums as m, and define f[i][j] as the maximum sum of selecting j non-adjacent numbers in the first i numbers of array nums.
Consider f[i][j], if we do not select the i-th number, then f[i][j] = f[i - 1][j]. If we select the i-th number, then f[i][j] = f[i - 2][j - 1] + nums[i - 1]. Therefore, we can get the state transition equation:
$
f[i][j] = max(f[i - 1][j], f[i - 2][j - 1] + nums[i - 1])
Finally, return f[m][n].
The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of the array slices$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming - Circular Array | Time Complexity: O(n^2), where n is the number of slices. Space Complexity: O(n^2) for the DP table. |
| Approach 2: Dynamic Programming with Space Optimization | Time Complexity: O(n^2), Space Complexity: O(n), where n is the number of slices. |
| Dynamic Programming | — |
| 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 |
Lecture 121: Pizza with 3n Slices || 2D - DP || DP Series • CodeHelp - by Babbar • 43,739 views views
Watch 7 more video solutions →Practice Pizza With 3n Slices with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor