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.

Learn more about Greedy, Dynamic Programming and Heap (Priority Queue) patterns.

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.

Solution Implementation

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

Learn more about how to find time and space complexity quickly using problem constraints.