Pizza With 3n Slices

Hard

#1286Time: O(m * n) or O(m^2) since `n = m/3`. We run the `solve` function twice, and each call involves nested loops of size `m-1` and `n`.Space: O(m * n) or O(m^2). The space is dominated by the 2D DP table of size `(m-1+1) x (n+1)`.

Patterns

Dynamic Programming Greedy

Data structures

Array Heap (Priority Queue)

Prompt

There is a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows:

You will pick any pizza slice.
Your friend Alice will pick the next slice in the anti-clockwise direction of your pick.
Your friend Bob will pick the next slice in the clockwise direction of your pick.
Repeat until there are no more slices of pizzas.

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.length
1 <= slices.length <= 500
1 <= slices[i] <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

The problem can be rephrased as "select n non-adjacent slices from a circular array of 3n slices to maximize the sum". The circular nature means the first and last slices are adjacent and cannot be picked together. This constraint can be handled by breaking the problem into two independent subproblems for a linear array:

Maximum sum from slices 0 to 3n-2.
Maximum sum from slices 1 to 3n-1. The final answer is the maximum of the solutions to these two subproblems. Each subproblem, which is to find the maximum sum of n non-adjacent items in a linear array, can be solved using dynamic programming.

Algorithm

Let m be the total number of slices and n = m / 3.
To handle the circular dependency, we solve two separate problems on linear arrays:
1. Find the max sum for slices[0...m-2].
2. Find the max sum for slices[1...m-1].
The overall answer is the maximum of the results of these two subproblems.
For each subproblem, we use a helper function solve(arr, k) which calculates the maximum sum of k non-adjacent elements from a linear array arr.
Inside solve, we use a 2D DP array dp[i][j] representing the max sum from the first i elements by picking j of them.
The DP table is filled using the recurrence: dp[i][j] = max(dp[i-1][j], arr[i-1] + dp[i-2][j-1]).
The result for a subproblem is dp[arr.length][k].

Walkthrough

Let's define a function solve(arr) that finds the maximum sum of n non-adjacent elements in a linear array arr. We use a 2D DP table, dp[i][j], to store the maximum sum we can obtain by choosing j slices from the first i slices of the input array arr. The state transition is as follows: For each slice arr[i-1] (using 1-based indexing for i), we have two choices:

Don't pick arr[i-1]: The maximum sum is the same as what we could get from the first i-1 slices by picking j slices. This value is dp[i-1][j].
Pick arr[i-1]: If we pick arr[i-1], we cannot pick its neighbor arr[i-2]. So, we must have picked j-1 slices from the first i-2 slices. The sum would be arr[i-1] + dp[i-2][j-1]. The recurrence relation is: dp[i][j] = max(dp[i-1][j], arr[i-1] + dp[i-2][j-1]). The base cases are dp[0][j] = 0 and dp[i][0] = 0. The final result for a subproblem of length L is dp[L][n].

1public class Solution {2    public int maxSizeSlices(int[] slices) {3        int m = slices.length;4        int n = m / 3;5        6        // Case 1: Exclude the last slice7        int[] slices1 = new int[m - 1];8        System.arraycopy(slices, 0, slices1, 0, m - 1);9        int ans1 = solve(slices1, n);10        11        // Case 2: Exclude the first slice12        int[] slices2 = new int[m - 1];13        System.arraycopy(slices, 1, slices2, 0, m - 1);14        int ans2 = solve(slices2, n);15        16        return Math.max(ans1, ans2);17    }18    19    private int solve(int[] arr, int k) {20        int len = arr.length;21        int[][] dp = new int[len + 1][k + 1];22        23        for (int i = 1; i <= len; i++) {24            for (int j = 1; j <= k; j++) {25                int notPick = dp[i - 1][j];26                int pick = (i >= 2 ? dp[i - 2][j - 1] : 0) + arr[i - 1];27                // It's impossible to pick j items from less than 2j-1 items.28                // This is implicitly handled if we consider that dp[i-2][j-1] would be 029                // if it was impossible to form that sum.30                // A more robust way is to check explicitly.31                if (2 * j > i + 1) { // or 2*j-1 > i32                    dp[i][j] = dp[i-1][j];33                } else {34                    dp[i][j] = Math.max(pick, notPick);35                }36            }37        }38        39        return dp[len][k];40    }41}

Complexity

Time

O(m * n) or O(m^2) since `n = m/3`. We run the `solve` function twice, and each call involves nested loops of size `m-1` and `n`.

Space

O(m * n) or O(m^2). The space is dominated by the 2D DP table of size `(m-1+1) x (n+1)`.

Trade-offs

Pros

It's a standard and clear dynamic programming solution that correctly solves the problem.
The logic is a direct translation of the recurrence relation.

Cons

The space complexity is O(m*n), which can be large for the given constraints, although it fits within typical memory limits.

This approach builds upon the previous DP solution by optimizing its space complexity. In the recurrence dp[i][j] = max(dp[i-1][j], arr[i-1] + dp[i-2][j-1]), we can observe that the computation for the current row i only depends on the two preceding rows, i-1 and i-2. This allows us to avoid storing the entire 2D DP table and instead only keep track of the last two rows.

Algorithm

The overall structure is identical to the first approach: solve two linear subproblems for slices[0...m-2] and slices[1...m-1].
The solve(arr, k) function is optimized for space.
Initialize two 1D arrays, prev2 and prev1, of size k+1 to represent the DP states for rows i-2 and i-1.
Iterate i from 1 to arr.length. In each iteration:
- Create a new 1D array curr of size k+1 for the current row i.
- Iterate j from 1 to k and compute curr[j] = max(prev1[j], arr[i-1] + prev2[j-1]), with a check for feasibility.
- After the inner loop, update prev2 = prev1 and prev1 = curr.
The result for the subproblem is prev1[k].

Walkthrough

The core idea remains the same: break the circular array problem into two linear array subproblems. The optimization lies within the solve helper function. Instead of a (len+1) x (k+1) DP table, we use three 1D arrays, say prev2, prev1, and curr, each of size k+1.

prev2 stores the DP values for row i-2.
prev1 stores the DP values for row i-1.
curr is used to compute the DP values for the current row i.

The update rule becomes: curr[j] = max(prev1[j], arr[i-1] + prev2[j-1]). After iterating through all j for a given i, we update the pointers for the next iteration: prev2 becomes prev1, and prev1 becomes curr. This rolling array mechanism reduces the space from O(m*n) to O(n).

1public class Solution {2    public int maxSizeSlices(int[] slices) {3        int m = slices.length;4        int n = m / 3;5        6        int[] slices1 = new int[m - 1];7        System.arraycopy(slices, 0, slices1, 0, m - 1);8        int ans1 = solve(slices1, n);9        10        int[] slices2 = new int[m - 1];11        System.arraycopy(slices, 1, slices2, 0, m - 1);12        int ans2 = solve(slices2, n);13        14        return Math.max(ans1, ans2);15    }16    17    private int solve(int[] arr, int k) {18        int len = arr.length;19        if (k == 0) {20            return 0;21        }22        23        int[] prev2 = new int[k + 1]; // Corresponds to dp[i-2]24        int[] prev1 = new int[k + 1]; // Corresponds to dp[i-1]25        26        for (int i = 1; i <= len; i++) {27            int[] curr = new int[k + 1]; // Corresponds to dp[i]28            for (int j = 1; j <= k; j++) {29                if (2 * j - 1 > i) {30                    curr[j] = prev1[j];31                } else {32                    int notPick = prev1[j];33                    int pick = arr[i - 1] + prev2[j - 1];34                    curr[j] = Math.max(pick, notPick);35                }36            }37            prev2 = prev1;38            prev1 = curr;39        }40        41        return prev1[k];42    }43}

Complexity

Time

O(m * n) or O(m^2). The number of computations is the same as the unoptimized version.

Space

O(n) or O(m). We only need to store a few arrays of size `n+1` to compute the result.

Trade-offs

Pros

Highly efficient in terms of space, reducing it from quadratic to linear.
Maintains the same time efficiency as the unoptimized DP approach.

Cons

The implementation can be slightly trickier to get right due to managing the rolling arrays.

Solutions

Solution

1class Solution {2private3  int n;4public5  int maxSizeSlices(int[] slices) {6    n = slices.length / 3;7    int[] nums = new int[slices.length - 1];8    System.arraycopy(slices, 1, nums, 0, nums.length);9    int a = g(nums);10    System.arraycopy(slices, 0, nums, 0, nums.length);11    int b = g(nums);12    return Math.max(a, b);13  }14private15  int g(int[] nums) {16    int m = nums.length;17    int[][] f = new int[m + 1][n + 1];18    for (int i = 1; i <= m; ++i) {19      for (int j = 1; j <= n; ++j) {20        f[i][j] =21            Math.max(f[i - 1][j], (i >= 2 ? f[i - 2][j - 1] : 0) + nums[i - 1]);22      }23    }24    return f[m][n];25  }26}

1class Solution {2public:3  int maxSizeSlices(vector<int> &slices) {4    int n = slices.size() / 3;5    auto g = [&](vector<int> &nums) -> int {6      int m = nums.size();7      int f[m + 1][n + 1];8      memset(f, 0, sizeof f);9      for (int i = 1; i <= m; ++i) {10        for (int j = 1; j <= n; ++j) {11          f[i][j] =12              max(f[i - 1][j], (i >= 2 ? f[i - 2][j - 1] : 0) + nums[i - 1]);13        }14      }15      return f[m][n];16    };17    vector<int> nums(slices.begin(), slices.end() - 1);18    int a = g(nums);19    nums = vector<int>(slices.begin() + 1, slices.end());20    int b = g(nums);21    return max(a, b);22  }23};

1class Solution:2    def maxSizeSlices(self, slices: List[int]) -> int: def g(nums: List[int]) -> int: m = len(nums) f = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): f[i][j] = max(f[i - 1][j], (f[i - 2][j - 1] if i >= 2 else 0) + nums[i - 1]) return f[m][n] n = len(slices) // 3 a, b = g(slices[: - 1]), g(slices[1:]) return max(a, b)

Video 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.

← Previous

Previous problem

Next problem