Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1388. Pizza With 3n Slices - Leetcode Solution

Code Implementation

class Solution:
    def maxSizeSlices(self, slices):
        def dp(slices):
            n = len(slices)
            choose = n // 3
            # dp[i][j]: max sum for first i slices, picking j slices
            dp = [[0] * (choose + 1) for _ in range(n + 1)]
            for i in range(1, n + 1):
                for j in range(1, choose + 1):
                    # Either pick i-th slice or not
                    dp[i][j] = max(
                        dp[i-1][j], 
                        (dp[i-2][j-1] if i >= 2 else 0) + slices[i-1]
                    )
            return dp[n][choose]
        # Since the pizza is circular, we can't take both first and last slices
        return max(dp(slices[1:]), dp(slices[:-1]))
      
class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        auto dp = [](const vector<int>& arr) {
            int n = arr.size();
            int choose = n / 3;
            vector<vector<int>> dp(n + 1, vector<int>(choose + 1, 0));
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= choose; ++j) {
                    dp[i][j] = max(
                        dp[i-1][j], 
                        (i >= 2 ? dp[i-2][j-1] : 0) + arr[i-1]
                    );
                }
            }
            return dp[n][choose];
        };
        vector<int> a(slices.begin() + 1, slices.end());
        vector<int> b(slices.begin(), slices.end() - 1);
        return max(dp(a), dp(b));
    }
};
      
class Solution {
    public int maxSizeSlices(int[] slices) {
        int n = slices.length;
        int choose = n / 3;

        return Math.max(
            helper(Arrays.copyOfRange(slices, 1, n), choose),
            helper(Arrays.copyOfRange(slices, 0, n - 1), choose)
        );
    }
    
    private int helper(int[] arr, int choose) {
        int n = arr.length;
        int[][] dp = new int[n + 1][choose + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= choose; ++j) {
                dp[i][j] = Math.max(
                    dp[i-1][j], 
                    (i >= 2 ? dp[i-2][j-1] : 0) + arr[i-1]
                );
            }
        }
        return dp[n][choose];
    }
}
      
var maxSizeSlices = function(slices) {
    function dp(arr) {
        const n = arr.length;
        const choose = Math.floor(n / 3);
        const dp = Array.from({length: n + 1}, () => Array(choose + 1).fill(0));
        for (let i = 1; i <= n; ++i) {
            for (let j = 1; j <= choose; ++j) {
                dp[i][j] = Math.max(
                    dp[i-1][j], 
                    (i >= 2 ? dp[i-2][j-1] : 0) + arr[i-1]
                );
            }
        }
        return dp[n][choose];
    }
    return Math.max(
        dp(slices.slice(1)),
        dp(slices.slice(0, slices.length - 1))
    );
};

Problem Description

You are given a circular pizza with 3n slices, where each slice has a positive integer size. There are three people (you and two friends), and you will pick slices in rounds, always picking first, then your friends pick optimally to minimize your total. In each round, you can only pick a slice that is not adjacent to any previously picked slice (since after a slice is picked, its neighbors are removed from the pizza). Your goal is to select exactly n slices (one-third of the pizza) such that the sum of their sizes is maximized, given that you cannot pick adjacent slices and the pizza is circular (the first and last slices are adjacent). The input is an array slices of length 3n, and you must return the maximum sum you can achieve by picking n non-adjacent slices.

Thought Process

At first glance, the problem looks similar to the classic "House Robber" problem, where you can't pick adjacent items. However, the twist here is that the pizza is circular (the first and last slices are adjacent), and you must pick exactly n slices out of 3n. A brute-force approach would try all possible combinations of n non-adjacent slices, but this is computationally infeasible due to the exponential number of possibilities. The challenge is further complicated by the circular nature of the pizza, which means choosing the first slice affects whether you can choose the last. This suggests a need for dynamic programming, and perhaps breaking the problem into two cases: one where you exclude the first slice, and one where you exclude the last slice, thereby "linearizing" the circle.

Solution Approach

We use dynamic programming to efficiently solve the problem. Here is the step-by-step approach:
  1. Break the problem into two linear subproblems:
    • If you pick the first slice, you can't pick the last slice (and vice versa).
    • So, compute the answer twice: once for slices[0..n*3-2] (excluding the last), and once for slices[1..n*3-1] (excluding the first).
  2. Set up the DP table:
    • Let dp[i][j] be the maximum sum for the first i slices, picking exactly j slices, with no two adjacent.
    • For each slice, you have two choices: skip it (dp[i-1][j]) or take it (dp[i-2][j-1] + slices[i-1]), if possible.
  3. Iterate and fill DP:
    • For each slice position i and pick count j, compute the best sum using the above choices.
    • Base cases: zero slices picked yields sum zero; can't pick more slices than available.
  4. Return the best answer:
    • The answer is the maximum of the two cases (excluding first or last slice).

Example Walkthrough

Let's consider slices = [1,2,3,4,5,6] (so n = 2).
  • Case 1: Exclude first slice ([2,3,4,5,6]), pick 2 non-adjacent slices.
    • Possible picks: 2 & 4, 2 & 6, 3 & 5, 3 & 6, 4 & 6.
    • Best sum: 6 + 4 = 10.
  • Case 2: Exclude last slice ([1,2,3,4,5]), pick 2 non-adjacent slices.
    • Possible picks: 1 & 3 = 4, 1 & 4 = 5, 2 & 4 = 6, 2 & 5 = 7, 3 & 5 = 8.
    • Best sum: 3 + 5 = 8.
  • Result: Maximum of 10 and 8 is 10.
The DP table fills up by making these choices for every subarray, ensuring we never pick adjacent slices and always pick exactly n slices.

Time and Space Complexity

  • Brute-force approach: Would try all combinations of n non-adjacent slices from 3n possibilities, which is exponential time and not feasible for large n.
  • Optimized DP approach:
    • Time Complexity: O(n^2), because for each of up to 3n slices, we process up to n possible picks.
    • Space Complexity: O(n^2) for the DP table.
The dynamic programming solution is efficient and suitable for the problem's constraints.

Summary

To solve "Pizza With 3n Slices," we used a dynamic programming approach inspired by the House Robber problem, but adapted for picking exactly n non-adjacent slices from a circular array. By splitting the problem into two linear cases (excluding the first or last slice), and building a DP table to maximize the sum for n picks, we efficiently found the optimal solution. This method balances careful state management with efficient computation, making it both elegant and practical.