1388. Pizza With 3n Slices


Problem Description

In this problem, we're given a circular arrangement of pizza slices represented by an integer array slices, where each element in the array corresponds to the size of a pizza slice. The slices are laid out in clockwise order, and there is a total of 3n slices, meaning the total number of slices is a multiple of three. The objective is to maximize the sum of sizes of slices that you can pick by following specified rules. The procedure for picking slices is as follows:

  1. You pick any slice of the pizza.
  2. Your friend Alice picks the next slice in an anti-clockwise direction from where you picked.
  3. Your friend Bob picks the next slice in a clockwise direction from where you picked.
  4. This process is repeated until no more slices are left.

The goal is to choose slices in such a way that the sum of the sizes of the slices you end up with is maximized.

Intuition

To approach this problem, we start by recognizing that it is a variation of the standard dynamic programming problem known as the "House Robber" problem. However, the twist here is that the arrangement of pizza slices is circular.

In a standard "House Robber" problem, you are trying to maximize the amount you rob from a line of houses without robbing two adjacent houses. Here, each pizza slice is like a "house," but since the pizza is circular, we have to prevent picking adjacent slices, and our choice wraps around the circle.

A key insight is that once we pick the first slice, the circular array problem reduces to two separate 'House Robber' problems:

  1. One in which the first slice is included and the last slice is excluded (to maintain non-adjacency), varying the position of the first slice.
  2. Another in which the first slice is excluded and the last slice is included.

We now can define a helper dynamic programming function g(nums), which takes a list of slices represented as a linear array nums and computes the maximum sum of sizes while adhering to the non-adjacent rule (similar to the 'House Robber' problem).

The state f[i][j] in the DP table represents the maximum sum we can obtain by considering up to the i-th pizza slice (0-indexed) and having picked j slices. For the i-th slice, we have two options: to take it or not. If we take it, we add its size to our total and look back two elements in the sequence to avoid adjacency, i.e., f[i - 2][j - 1] + nums[i - 1]. If we don't take it, we simply move to the previous element without changing the number of picked elements, i.e., f[i - 1][j]. We choose the option that yields the higher sum.

Finally, we run this helper function on the two separate scenarios (including the first slice and excluding the last, and vice-versa) and return the maximum sum obtained from both runs.

Solution Approach

The solution approach builds upon the dynamic programming pattern for solving optimization problems, particularly those related to making choices in sequences with constraints, like the "House Robber" problem. In this problem, the circular nature of the pizza slices array imposes a unique constraint, which we address by dividing the problem into two linear subproblems.

The helper function g(nums) takes as input a linear array of pizza slices sizes and returns the maximum sum we can achieve by picking non-adjacent slices. It uses a two-dimensional dynamic programming array f, where f[i][j] represents the maximum sum by considering up to the i-th slice (1-indexed in the explanation but 0-indexed in code) and having selected j slices.

The following algorithmic steps are taken within the g(nums) function:

  1. Initialize a DP table f with dimensions (m + 1) x (n + 1), where m is the length of the input list nums, and n is one-third of the length of the original slices array, representing the maximum number of slices you can choose.
  2. Iterate over the slices array with an outer loop going from 1 to m and an inner loop going from 1 to n.
  3. For each i and j, determine the maximum sum that can be achieved by either including or excluding the current slice:
    • If the slice is excluded, the value remains f[i - 1][j].
    • If the slice is included, it's the sum of the current slice's value nums[i - 1] and the value from two steps back (to avoid adjacency) f[i - 2][j - 1], or 0 if i is less than 2.
  4. Ensure that each entry f[i][j] contains the maximum sum obtainable up to that point by choosing the maximum value between including and excluding the current slice.

After defining the helper function, we apply it to two scenarios: slices[:-1] and slices[1:]. This corresponds to two cases — when we include the first slice and exclude the last one, and when we exclude the first slice and include the last one. This effectively deals with the circular arrangement by treating it as two separate linear arrays.

The final result returned by the maxSizeSlices function is the maximum value obtained from both scenarios, achieved by calling max(a, b) where a and b are the results from the helper function g on the two subarrays.

In conclusion, the dynamic programming approach offers an efficient way to tackle this problem by reducing it to simpler subproblems and combining the results of these subproblems to obtain the final solution, which guarantees maximum sum of pizza slices you can pick.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have a circular array of pizza slices slices = [1, 5, 3, 4, 2, 3], meaning there are 3n = 6 slices in total.

We will use the helper function g(nums) described in the solution approach to solve two separate 'House Robber' subproblems:

  • The first subproblem includes the first slice and excludes the last, so we consider nums = [1, 5, 3, 4].
  • The second subproblem excludes the first slice and includes the last, so we consider nums = [5, 3, 4, 2].

For each of these arrays, our dynamic programming table f[i][j] calculates the maximum sum obtainable by selecting j slices when considering up to the i-th slice. Let us walk through solving one of these subproblems: nums = [1, 5, 3, 4].

We initialize a DP table f with dimensions (4 + 1) x (2 + 1), since m = 4 (the number of elements in nums) and n = 2 (we can choose at most 6/3 = 2 slices).

The DP table is initially filled with zeros:

f = [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

Now we start filling the table:

  1. For i = 1, we cannot select the first slice as there are no previous slices to compare with. So f[1][1] would just be the value of the first slice (1 here).
  2. For i = 2, we can either take the current slice (5) or the previous slice (1), but not both. We take 5 because it is the higher value: f[2][1] = 5.
  3. As we move to i = 3, we look at including slice 3, which means we add 3 to f[1][1] (since selecting slice 3 means we cannot select slice 5), or we exclude it, which means we carry over the 5 from f[2][1].

Here is the table with values filled:

1f = [
2[0, 0, 0], 
3[0, 1, 0],  // i = 1
4[0, 5, 0],  // i = 2
5[0, 5, 0],  // i = 3, 1st pass
6[0, 0, 0]   // i = 4, placeholders for now
7]

For i = 3, j = 2, we consider the 3rd slice (value 3). We can't include it since j = 2 and we've already selected one slice (j doesn't increase). So, f[3][2] carries the value from f[2][2].

Continuing in a similar way, we fill the table for i = 4. If we include slice 4, we must add its value (4) to f[2][1] (5), which gives us 9 for f[4][2]. We complete the DP table:

1f = [
2[0, 0, 0], 
3[0, 1, 0], 
4[0, 5, 0], 
5[0, 5, 5], 
6[0, 5, 9]
7]

The maximum sum we can obtain for nums = [1, 5, 3, 4] is f[4][2] = 9.

We would run the same process for nums = [5, 3, 4, 2] and let's say we get a maximum sum of f[4][2] = 10.

The result of our maxSizeSlices function will be the maximum value between the two subproblems, which is max(9, 10) = 10. Thus, by applying the solution approach on the given circular array of pizza slices, we deduce that the maximum sum of the sizes of the slices we can pick is 10.

By breaking it down into simpler, non-circular arrays and using the helper dynamic programming function g(nums), we have managed to solve the problem efficiently.

Python Solution

1from typing import List
2
3class Solution:
4    def max_size_slices(self, slices: List[int]) -> int:
5        # Helper function to calculate the maximum sum of non-adjacent slices
6        def calculate_max_sum(nums: List[int]) -> int:
7            slice_count = len(nums)
8            # The number of slices to be taken is one-third of the total number of slices provided
9            take_slices = len(slices) // 3
10            # Initialize a 2D array to store subproblem solutions
11            dp = [[0] * (take_slices + 1) for _ in range(slice_count + 1)]
12          
13            # Populate the dp array with maximum sum values for each subproblem
14            for i in range(1, slice_count + 1):
15                for j in range(1, take_slices + 1):
16                    # The max of either not taking the current slice or taking it (and skipping the adjacent one)
17                    dp[i][j] = max(
18                        dp[i - 1][j],
19                        (dp[i - 2][j - 1] if i >= 2 else 0) + nums[i - 1]
20                    )
21            return dp[slice_count][take_slices]
22
23        # Since we cannot take adjacent slices and we can't take the first and last together,
24        # we perform the calculation twice—once without the first slice and once without the last slice
25        max_sum_exclude_first = calculate_max_sum(slices[:-1])
26        max_sum_exclude_last = calculate_max_sum(slices[1:])
27      
28        # Return the maximum of the two calculated sums
29        return max(max_sum_exclude_first, max_sum_exclude_last)
30
31# Example to use the class and method
32# solution = Solution()
33# print(solution.max_size_slices([1,2,3,4,5,6])) # Example usage with an array of pizza slices
34

Java Solution

1class Solution {
2  
3    private int n; // Number of slices to pick
4
5    // Function to return the maximum sum of slices
6    public int maxSizeSlices(int[] slices) {
7        n = slices.length / 3; // Calculate the number of slices we can pick
8        // Initialize an array to store slices without the first element
9        int[] slicesWithoutFirst = new int[slices.length - 1];
10        // Copy the array `slices` to `slicesWithoutFirst` starting from the second element
11        System.arraycopy(slices, 1, slicesWithoutFirst, 0, slicesWithoutFirst.length);
12        int maxSumExcludingFirst = calculateMaxSum(slicesWithoutFirst);
13      
14        // Initialize another array to store slices without the last element
15        int[] slicesWithoutLast = new int[slices.length - 1];
16        // Copy the array `slices` to `slicesWithoutLast` up to the second-to-last element
17        System.arraycopy(slices, 0, slicesWithoutLast, 0, slicesWithoutLast.length);
18        int maxSumExcludingLast = calculateMaxSum(slicesWithoutLast);
19      
20        // Return the maximum sum of two cases (excluding the first slice or the last slice)
21        return Math.max(maxSumExcludingFirst, maxSumExcludingLast);
22    }
23
24    // Helper function to calculate the maximum sum using dynamic programming
25    private int calculateMaxSum(int[] nums) {
26        int numsLength = nums.length;
27        // `dp` array where `dp[i][j]` represents the max sum using first `i` slices and `j` picks
28        int[][] dp = new int[numsLength + 1][n + 1];
29        for (int i = 1; i <= numsLength; ++i) {
30            for (int j = 1; j <= n; ++j) {
31                // Choose the bigger between not taking or taking the current slice
32                dp[i][j] = Math.max(dp[i - 1][j], 
33                                    (i >= 2 ? dp[i - 2][j - 1] : 0) + nums[i - 1]);
34            }
35        }
36        // Return the maximum sum for `numsLength` slices and `n` picks
37        return dp[numsLength][n];
38    }
39}
40

C++ Solution

1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7    int maxSizeSlices(vector<int>& slices) {
8        // Determine the size of a set (n) we want to calculate, which is one-third of the total slices
9        int n = slices.size() / 3;
10      
11        // Lambda function to calculate the maximum size of pizza slices using dynamic programming
12        auto getMaxSize = [&](vector<int>& nums) -> int {
13            int m = nums.size(); // Number of elements in the current pizza slice array
14            int dp[m + 1][n + 1]; // dp[i][j] will store the max size when considering i slices for j sets
15          
16            // Initialize the dynamic programming array to 0
17            memset(dp, 0, sizeof(dp));
18          
19            // Build the dp array using previous computed values
20            for (int i = 1; i <= m; ++i) {
21                for (int j = 1; j <= n; ++j) {
22                    // Either take the current slice and add the best of i-2 for j-1 sets or skip the current slice
23                    dp[i][j] = std::max(dp[i - 1][j], (i >= 2 ? dp[i - 2][j - 1] : 0) + nums[i - 1]);
24                }
25            }
26            // Return the maximum size possible for the current pizza slices array
27            return dp[m][n];
28        };
29      
30        // Calculate the max size for two cases to avoid circle adjacency:
31        // Case 1: Include all slices except the last
32        vector<int> nums(slices.begin(), slices.end() - 1);
33        int maxWithoutLast = getMaxSize(nums);
34      
35        // Case 2: Include all slices except the first
36        nums = vector<int>(slices.begin() + 1, slices.end());
37        int maxWithoutFirst = getMaxSize(nums);
38      
39        // Return the maximum size by comparing the two cases
40        return std::max(maxWithoutLast, maxWithoutFirst);
41    }
42};
43

Typescript Solution

1function maxSizeSlices(slices: number[]): number {
2    // Calculate the number of slices to select, which is one third of the total slices.
3    const selectCount = Math.floor(slices.length / 3);
4
5    // Helper function to calculate the maximum size of slices from a given subarray.
6    const calculateMaxSize = (nums: number[]): number => {
7        const length = nums.length;
8        const dp: number[][] = Array.from({ length: length + 1 }, () => Array(selectCount + 1).fill(0));
9
10        // Populate the dynamic programming table with the maximum sizes.
11        for (let i = 1; i <= length; ++i) {
12            for (let j = 1; j <= selectCount; ++j) {
13                dp[i][j] = Math.max(
14                  dp[i - 1][j], // Previous state without current slice
15                  // Add current slice only if we have more than 1 pizza slice (to skip adjacent)
16                  (i > 1 ? dp[i - 2][j - 1] : 0) + nums[i - 1]
17                );
18            }
19        }
20
21        // Return the maximum size for the given subarray
22        return dp[length][selectCount];
23    };
24
25    // Calculate the maximum size by taking two cases
26    // 1. Excluding the last slice
27    // 2. Excluding the first slice
28    // Since the pizza is circular, we cannot take the first and last slices together.
29    const maxWithFirstExcluded = calculateMaxSize(slices.slice(0, -1));
30    const maxWithLastExcluded = calculateMaxSize(slices.slice(1));
31
32    // Return the maximum of the two cases
33    return Math.max(maxWithFirstExcluded, maxWithLastExcluded);
34}
35

Time and Space Complexity

The given code defines a function g(nums: List[int]) -> int that calculates the maximum sum of n non-adjacent elements in a list nums using dynamic programming. This function is called twice on two different slices of the input list slices in order to account for the circular nature of the problem by excluding the first or the last element.

Time Complexity:

The time complexity of the function g is determined by the nested loops. There are two loops:

  • The outer loop runs m times, where m is the length of the input list nums.
  • The inner loop runs n times, where n = len(slices) // 3.

Inside the inner loop, only constant-time operations are performed. Therefore, the overall time complexity for function g is O(m * n). Since g is called twice, once for slices[:-1] and once for slices[1:], the time complexity of the entire maxSizeSlices function remains the same, as both slices have a length very close to the original length (len(slices) - 1). Thus, the time complexity for the maxSizeSlices function is also O(m * n), where m is nearly equal to len(slices).

Space Complexity:

Space complexity is determined by the amount of extra space used by the algorithm, which in this case is primarily due to the 2D array f defined in function g.

  • The 2D array f has dimensions (m + 1) * (n + 1), where m is the length of nums and n = len(slices) // 3.

Therefore, the space complexity of function g is O(m * n). Since the space used by f is reused when g is called the second time, the space complexity of the entire maxSizeSlices function is also O(m * n). Here, m is nearly equal to len(slices).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫