LeetCode 1388 - Pizza With 3n Slices

In this problem, we are given a circular pizza divided into 3n slices. Each slice has a size represented by the array sl

leetcodehardarraydynamic-programminggreedyheap-(priority-queue)

LeetCode Problem 1388

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

In this problem, we are given a circular pizza divided into 3n slices. Each slice has a size represented by the array slices, where the values are listed in clockwise order.

You repeatedly perform the following process:

  1. You choose any remaining slice.
  2. Alice immediately takes the slice directly anti-clockwise from your chosen slice.
  3. Bob immediately takes the slice directly clockwise from your chosen slice.

This continues until no slices remain.

Because every round removes exactly three slices, and the pizza initially contains 3n slices, you will ultimately choose exactly n slices.

The goal is to maximize the total size of the slices you personally pick.

The most important observation is that whenever you choose a slice, its two neighboring slices become unavailable. This means the slices you choose can never be adjacent. Since the pizza is circular, the first and last slices are also adjacent.

So the problem becomes:

Select exactly n non-adjacent slices from a circular array of length 3n such that their total sum is maximized.

The constraints are important:

  • slices.length <= 500
  • Each slice value is at most 1000

A brute-force search over all combinations would be far too slow because the number of possible selections grows exponentially. The relatively small input size suggests that a dynamic programming solution is expected.

There are several edge cases that can easily break naive implementations:

  • Since the pizza is circular, selecting the first slice prevents selecting the last slice.
  • We must choose exactly n slices, not fewer.
  • Greedy selection does not work because a large slice may block multiple valuable choices nearby.
  • Arrays with repeated values can create many equivalent-looking choices that still require careful optimization.

The problem guarantees:

  • The array length is always divisible by 3.
  • Every slice size is positive.
  • There is always at least one valid solution.

Approaches

Brute Force Approach

A brute-force solution would try every possible subset of slices and check whether:

  1. Exactly n slices were selected.
  2. No two selected slices are adjacent in the circular arrangement.

For every valid subset, we compute the total sum and keep the maximum.

This approach is correct because it explicitly checks every possible valid selection. However, it is computationally infeasible.

If the array contains m = 3n elements, then there are 2^m subsets. With m = 500, this becomes astronomically large.

Even with pruning, the search space remains exponential.

Optimal Dynamic Programming Approach

The key insight is that this problem is essentially a variation of the classic:

Maximum sum of non-adjacent elements in a circular array with exactly k selections.

Circular adjacency is the main complication. In a linear array, dynamic programming is straightforward because only neighboring indices matter.

To handle the circular structure, we split the problem into two independent linear cases:

  1. Exclude the first slice.
  2. Exclude the last slice.

Why does this work?

In a circular array, the first and last elements cannot both be selected. Therefore, every valid solution must belong to one of these two categories:

  • Solutions that do not use the first slice.
  • Solutions that do not use the last slice.

For each linear case, we solve:

Pick exactly n non-adjacent elements with maximum total sum.

We use dynamic programming where:

  • dp[i][j] represents the maximum sum obtainable using the first i elements while selecting exactly j slices.

For each position, we either:

  • Skip the current slice.
  • Take the current slice, which forces us to skip the previous one.

This produces an efficient polynomial-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(3n)) O(3n) Tries every possible subset
Optimal O(n^2) O(n^2) Dynamic programming on two linear cases

Algorithm Walkthrough

Step 1: Determine How Many Slices We Must Pick

If the pizza contains 3n slices, then we will ultimately choose exactly:

k = len(slices) // 3

This value is fixed throughout the problem.

Step 2: Convert the Circular Problem Into Two Linear Problems

Because the pizza is circular, the first and last slices are adjacent.

We cannot select both simultaneously.

So we solve two separate cases:

  1. Use slices from index 0 to n-2
  2. Use slices from index 1 to n-1

Then we take the maximum result.

This guarantees that every valid solution is considered exactly once.

Step 3: Define the DP State

For a linear array arr, define:

dp[i][j]

as:

The maximum sum obtainable using the first i elements while selecting exactly j non-adjacent slices.

The dimensions are:

  • i ranges from 0 to len(arr)
  • j ranges from 0 to k

Step 4: Transition Between States

At each position, we have two choices.

Option 1: Skip Current Slice

If we do not take the current slice:

dp[i][j] = dp[i-1][j]

Option 2: Take Current Slice

If we take the current slice:

  • We add its value.
  • We must skip the previous slice.

So:

dp[i][j] = dp[i-2][j-1] + arr[i-1]

We take the maximum of these two choices.

Step 5: Fill the DP Table

We iterate through all indices and all possible selection counts.

Care must be taken for boundary cases where i < 2.

Step 6: Solve Both Cases

Compute:

  • Best result excluding last slice
  • Best result excluding first slice

Return the larger value.

Why it works

The dynamic programming recurrence guarantees optimality because every valid solution for position i must either include the current slice or exclude it.

If we include it, adjacency rules force us to skip the previous slice, reducing the problem to an optimal subproblem ending at i-2.

If we exclude it, the problem reduces to the optimal subproblem ending at i-1.

Since the circular constraint only affects the relationship between the first and last slices, splitting into two linear cases fully captures all valid possibilities.

Python Solution

from typing import List

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        choose = len(slices) // 3

        def solve(arr: List[int]) -> int:
            n = len(arr)

            dp = [[0] * (choose + 1) for _ in range(n + 1)]

            for i in range(1, n + 1):
                for j in range(1, choose + 1):
                    # Skip current slice
                    dp[i][j] = dp[i - 1][j]

                    # Take current slice
                    current = arr[i - 1]

                    if i >= 2:
                        dp[i][j] = max(
                            dp[i][j],
                            dp[i - 2][j - 1] + current
                        )
                    else:
                        dp[i][j] = max(
                            dp[i][j],
                            current
                        )

            return dp[n][choose]

        # Case 1: exclude last slice
        case1 = solve(slices[:-1])

        # Case 2: exclude first slice
        case2 = solve(slices[1:])

        return max(case1, case2)

The implementation begins by computing how many slices we must choose. Since the pizza contains 3n slices, we must select exactly n slices.

The helper function solve() handles the linear version of the problem. It receives a normal array where the first and last elements are no longer adjacent.

The DP table stores the best possible sum for every prefix length and every possible number of chosen slices.

For each position:

  • We first assume we skip the current slice.
  • Then we consider taking it.

If we take the current slice, we must move back two positions because adjacent slices cannot both be selected.

Finally, we solve the two circular cases separately:

  • Excluding the last slice
  • Excluding the first slice

The maximum of these two results is the final answer.

Go Solution

func maxSizeSlices(slices []int) int {
	choose := len(slices) / 3

	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}

	solve := func(arr []int) int {
		n := len(arr)

		dp := make([][]int, n+1)
		for i := range dp {
			dp[i] = make([]int, choose+1)
		}

		for i := 1; i <= n; i++ {
			for j := 1; j <= choose; j++ {
				// Skip current slice
				dp[i][j] = dp[i-1][j]

				// Take current slice
				current := arr[i-1]

				if i >= 2 {
					dp[i][j] = max(
						dp[i][j],
						dp[i-2][j-1]+current,
					)
				} else {
					dp[i][j] = max(
						dp[i][j],
						current,
					)
				}
			}
		}

		return dp[n][choose]
	}

	case1 := solve(slices[:len(slices)-1])
	case2 := solve(slices[1:])

	return max(case1, case2)
}

The Go implementation follows the same logic as the Python version.

The primary difference is explicit slice and memory management. The DP table is created using nested slices.

Go does not provide a built-in max function for integers, so a helper function is defined manually.

Because all values are small and the maximum possible sum is well within 32-bit integer range, standard int arithmetic is sufficient.

Worked Examples

Example 1

Input: [1,2,3,4,5,6]

We must select:

6 / 3 = 2 slices

Case 1: Exclude Last Slice

Array becomes:

[1,2,3,4,5]

We now solve:

Pick 2 non-adjacent slices with maximum sum.

Selected Slices Sum
1 + 3 4
1 + 4 5
1 + 5 6
2 + 4 6
2 + 5 7
3 + 5 8

Best result:

8

Case 2: Exclude First Slice

Array becomes:

[2,3,4,5,6]

Possible selections:

Selected Slices Sum
2 + 4 6
2 + 5 7
2 + 6 8
3 + 5 8
3 + 6 9
4 + 6 10

Best result:

10

Final answer:

max(8, 10) = 10

Example 2

Input: [8,9,8,6,1,1]

We must pick:

2 slices

Case 1: Exclude Last Slice

[8,9,8,6,1]

Best valid selection:

8 + 8 = 16

Case 2: Exclude First Slice

[9,8,6,1,1]

Best valid selection:

9 + 1 = 10

Final answer:

max(16, 10) = 16

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) DP table has O(n × k) states
Space O(n^2) DP table stores all states

Let m = len(slices).

We select:

k = m / 3

For each of the two linear cases, we compute a DP table of size:

m × k

Since k is proportional to m, the complexity becomes quadratic.

With m <= 500, this is efficient enough.

Test Cases

from typing import List

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        choose = len(slices) // 3

        def solve(arr: List[int]) -> int:
            n = len(arr)

            dp = [[0] * (choose + 1) for _ in range(n + 1)]

            for i in range(1, n + 1):
                for j in range(1, choose + 1):
                    dp[i][j] = dp[i - 1][j]

                    current = arr[i - 1]

                    if i >= 2:
                        dp[i][j] = max(
                            dp[i][j],
                            dp[i - 2][j - 1] + current
                        )
                    else:
                        dp[i][j] = max(dp[i][j], current)

            return dp[n][choose]

        return max(
            solve(slices[:-1]),
            solve(slices[1:])
        )

sol = Solution()

assert sol.maxSizeSlices([1,2,3,4,5,6]) == 10  # Example 1
assert sol.maxSizeSlices([8,9,8,6,1,1]) == 16  # Example 2
assert sol.maxSizeSlices([3,1,2]) == 3  # Smallest valid input
assert sol.maxSizeSlices([1,1,1,1,1,1]) == 2  # All equal values
assert sol.maxSizeSlices([9,1,1,9,1,1]) == 18  # Pick both large non-adjacent slices
assert sol.maxSizeSlices([4,1,2,5,8,3,1,9,7]) == 21  # Larger mixed case
assert sol.maxSizeSlices([1000,1,1,1000,1,1]) == 2000  # Large values
assert sol.maxSizeSlices([5,5,5,5,5,5,5,5,5]) == 15  # Repeated values
assert sol.maxSizeSlices([1,2,3,100,4,5]) == 105  # One dominant slice
assert sol.maxSizeSlices([7,7,7]) == 7  # Single selection only
Test Why
[1,2,3,4,5,6] Validates example 1
[8,9,8,6,1,1] Validates example 2
[3,1,2] Smallest possible valid input
[1,1,1,1,1,1] Tests repeated identical values
[9,1,1,9,1,1] Ensures non-adjacent large values are chosen
[4,1,2,5,8,3,1,9,7] General mixed scenario
[1000,1,1,1000,1,1] Tests large numbers
[5,5,5,5,5,5,5,5,5] Many equivalent optimal choices
[1,2,3,100,4,5] Greedy traps around a dominant value
[7,7,7] Minimal circular configuration

Edge Cases

One important edge case occurs when the array contains only three slices. In this situation, we can select exactly one slice. Because the pizza is circular, every slice is adjacent to the other two, so the answer is simply the maximum element. The implementation handles this naturally through the DP transitions.

Another tricky case occurs when the optimal solution includes slices near both ends of the array. Since the pizza is circular, the first and last slices cannot both be chosen. A naive linear DP would incorrectly allow this. The implementation avoids this by splitting the problem into two separate linear cases, one excluding the first slice and one excluding the last.

Arrays containing many equal values can also cause subtle bugs in greedy approaches. For example, selecting locally large values too early may block future selections unnecessarily. Dynamic programming correctly evaluates all possibilities and guarantees the globally optimal answer.

A final important edge case involves very large slice values. Since values may reach 1000 and the array length can be 500, the implementation must safely handle sums up to roughly 500000. Both Python integers and Go integers easily support this range without overflow issues.