1388. Pizza With 3n Slices - Solution

The problem

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

Approach overview

Problem Overview: You are given a circular array where the length is 3n. Each element represents the size of a pizza slice. You must pick exactly n slices such that no two chosen slices are adjacent. Because the pizza is circular, the first and last slices are also adjacent. The goal is to maximize the total size of the chosen slices.

Approach 1: Dynamic Programming - Circular Array (O(n^2) time, O(n^2) space)

The circular constraint means you cannot pick both the first and last slice. Handle this by splitting the problem into two linear cases: include slices [0 ... 3n-2] or include slices [1 ... 3n-1]. Each case becomes a classic non-adjacent selection problem similar to House Robber but with a fixed number of selections. Define dp[i][j] as the maximum sum using the first i slices while selecting j slices. For each slice, either skip it or take it and add its value to dp[i-2][j-1] since adjacent slices cannot be chosen. Compute this for both linear scenarios and return the larger result. The dynamic programming table iterates through slices and selection counts, producing a time complexity of O(n^2) and space complexity of O(n^2). This approach relies heavily on dynamic programming patterns and careful handling of the array boundaries.

Approach 2: Dynamic Programming with Space Optimization (O(n^2) time, O(n) space)

The previous solution stores the entire DP matrix, but each state only depends on earlier rows. You can compress the memory by keeping only the necessary previous states. Instead of maintaining a full dp[i][j] grid, use rolling arrays that track the last two slice states for every possible selection count. While iterating through the slices, update the current values based on the same recurrence: skip the slice or take it and add the value from two steps back. This reduces space from O(n^2) to O(n) while preserving the same transition logic. The algorithm still evaluates both linear ranges to handle the circular structure. This version is preferred when memory constraints matter and demonstrates deeper control over DP state transitions. Although the problem is sometimes associated with greedy intuition, the optimal solution requires structured DP to enforce the exact n selections.

Recommended for interviews: The dynamic programming circular array approach is what most interviewers expect. Explaining why the circular constraint forces two cases shows strong problem decomposition. Implementing the optimized DP version demonstrates mastery of state reduction and memory optimization.

Approach 1: Approach 1: Dynamic Programming - Circular Array

This approach utilizes dynamic programming to solve the problem of selecting non-consecutive maximum slices. Since the pizza is circular, we consider two possible scenarios: including the first slice and excluding the last one, and excluding the first slice and including the last one. We solve both scenarios using a dynamic programming table to store the maximum sum for slices that can be picked.

Python

def solve(slices, start, end, n):
    dp = [[0] * (n + 1) for _ in range(end - start + 2)]
    length = end - start + 1
    for i in range(length - 1, -1, -1):
        for j in range(1, min(n, length - i) + 1):
            dp[i][j] = max(dp[i + 1][j], slices[start + i] + (dp[i + 2][j - 1] if i + 2 <= length else 0))
    return dp[0][n]


def maxSizeSlices(slices):
    n = len(slices) // 3
    return max(solve(slices, 0, len(slices) - 2, n), solve(slices, 1, len(slices) - 1, n))


slices = [8, 9, 8, 6, 1, 1]
print(maxSizeSlices(slices))

Java

import java.util.*;

public class MaxSizeSlices {
    public int solve(int[] slices, int start, int end, int n) {
        int[][] dp = new int[end - start + 2][n + 1];
        int len = end - start + 1;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = 1; j <= Math.min(n, len - i); j++) {
                dp[i][j] = Math.max(dp[i + 1][j], slices[start + i] + (i + 2 <= len ? dp[i + 2][j - 1] : 0));
            }
        }
        return dp[0][n];
    }

    public int maxSizeSlices(int[] slices) {
        int n = slices.length / 3;
        return Math.max(solve(slices, 0, slices.length - 2, n), solve(slices, 1, slices.length - 1, n));
    }

    public static void main(String[] args) {
        MaxSizeSlices solution = new MaxSizeSlices();
        int[] slices = {8, 9, 8, 6, 1, 1};
        System.out.println(solution.maxSizeSlices(slices));
    }
}

C++

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solve(const vector<int>& slices, int start, int end, int n) {
    vector<vector<int>> dp(end - start + 2, vector<int>(n + 1, 0));
    int len = end - start + 1;
    for (int i = len - 1; i >= 0; --i) {
        for (int j = 1; j <= min(n, len - i); ++j) {
            dp[i][j] = max(dp[i + 1][j], slices[start + i] + (i + 2 <= len ? dp[i + 2][j - 1] : 0));
        }
    }
    return dp[0][n];
}

int maxSizeSlices(vector<int>& slices) {
    int n = slices.size() / 3;
    return max(solve(slices, 0, slices.size() - 2, n), solve(slices, 1, slices.size() - 1, n));
}

int main() {
    vector<int> slices = {8, 9, 8, 6, 1, 1};
    cout << maxSizeSlices(slices) << endl;
    return 0;
}

JavaScript

function solve(slices, start, end, n) {
    let dp = Array.from({ length: end - start + 2 }, () => Array(n + 1).fill(0));
    let length = end - start + 1;
    for (let i = length - 1; i >= 0; i--) {
        for (let j = 1; j <= Math.min(n, length - i); j++) {
            dp[i][j] = Math.max(dp[i + 1][j], slices[start + i] + (i + 2 <= length ? dp[i + 2][j - 1] : 0));
        }
    }
    return dp[0][n];
}

function maxSizeSlices(slices) {
    const n = Math.floor(slices.length / 3);
    return Math.max(solve(slices, 0, slices.length - 2, n), solve(slices, 1, slices.length - 1, n));
}

const slices = [8, 9, 8, 6, 1, 1];
console.log(maxSizeSlices(slices));

#include <stdio.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solve(int* slices, int start, int end, int n) {
    int dp[501][501];
    memset(dp, 0, sizeof(dp));
    int len = end - start + 1;
    for (int i = len - 1; i >= 0; --i) {
        int maxSlices = max(0, len - 1 - i);
        for (int j = 1; j <= maxSlices && j <= n; ++j) {
            dp[i][j] = max(dp[i + 1][j], (i + 2 <= len ? slices[start + i] + dp[i + 2][j - 1] : slices[start + i]));
        }
    }
    return dp[0][n];
}

int maxSizeSlices(int* slices, int slicesSize) {
    int n = slicesSize / 3;
    return max(solve(slices, 0, slicesSize - 2, n), solve(slices, 1, slicesSize - 1, n));
}

int main() {
    int slices[] = {8, 9, 8, 6, 1, 1};
    int size = sizeof(slices) / sizeof(slices[0]);
    printf("%d", maxSizeSlices(slices, size));
    return 0;
}

using System;

class MaxSizeSlices {
    int Solve(int[] slices, int start, int end, int n) {
        int[,] dp = new int[end - start + 2, n + 1];
        int len = end - start + 1;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = 1; j <= Math.Min(n, len - i); j++) {
                dp[i, j] = Math.Max(dp[i + 1, j], slices[start + i] + (i + 2 <= len ? dp[i + 2, j - 1] : 0));
            }
        }
        return dp[0, n];
    }

    public int MaxSizeSlices(int[] slices) {
        int n = slices.Length / 3;
        return Math.Max(Solve(slices, 0, slices.Length - 2, n), Solve(slices, 1, slices.Length - 1, n));
    }

    static void Main(string[] args) {
        MaxSizeSlices solution = new MaxSizeSlices();
        int[] slices = {8, 9, 8, 6, 1, 1};
        Console.WriteLine(solution.MaxSizeSlices(slices));
    }
}

This Python solution uses a DP table to consider maximum sum of chosen slices, ensuring that slices are not picked consecutively, except across the circular wrap of the pizza.

Complexity

Time Complexity: O(n^2), where n is the number of slices. Space Complexity: O(n^2) for the DP table.

Try this approach in the editor

Approach 2: Approach 2: Dynamic Programming with Space Optimization

This approach focuses on optimizing the space used in dynamic programming by maintaining just two previous states rather than a whole table. This can significantly reduce the space complexity from O(n^2) to O(n), improving the practicality of the solution when dealing with larger inputs.

Python

def solve(slices, start, end, n):
    prev2, prev1 = [0] * (n + 1), [0] * (n + 1)

    for i in range(end - start, -1, -1):
        current = [0] * (n + 1)
        for j in range(1, min(n, end - start + 1 - i) + 1):
            current[j] = max(prev1[j], slices[start + i] + prev2[j - 1])
        prev2, prev1 = prev1, current

    return prev1[n]


def maxSizeSlices(slices):
    n = len(slices) // 3
    return max(solve(slices, 0, len(slices) - 2, n), solve(slices, 1, len(slices) - 1, n))


slices = [8, 9, 8, 6, 1, 1]
print(maxSizeSlices(slices))

Java

public class MaxSizeSlicesOptimized {
    public int solve(int[] slices, int start, int end, int n) {
        int[] prev2 = new int[n + 1];
        int[] prev1 = new int[n + 1];

        for (int i = end - start; i >= 0; i--) {
            int[] current = new int[n + 1];
            for (int j = 1; j <= Math.min(n, end - start + 1 - i); j++) {
                current[j] = Math.max(prev1[j], slices[start + i] + prev2[j - 1]);
            }
            prev2 = prev1;
            prev1 = current;
        }
        return prev1[n];
    }

    public int maxSizeSlices(int[] slices) {
        int n = slices.length / 3;
        return Math.max(solve(slices, 0, slices.length - 2, n), solve(slices, 1, slices.length - 1, n));
    }

    public static void main(String[] args) {
        MaxSizeSlicesOptimized solution = new MaxSizeSlicesOptimized();
        int[] slices = {8, 9, 8, 6, 1, 1};
        System.out.println(solution.maxSizeSlices(slices));
    }
}

C++

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solve(const vector<int>& slices, int start, int end, int n) {
    vector<int> prev2(n + 1, 0);
    vector<int> prev1(n + 1, 0);
    int len = end - start + 1;

    for (int i = len - 1; i >= 0; --i) {
        vector<int> current(n + 1, 0);
        for (int j = 1; j <= min(n, len - i); ++j) {
            current[j] = max(prev1[j], slices[start + i] + prev2[j - 1]);
        }
        prev2 = prev1;
        prev1 = current;
    }

    return prev1[n];
}

int maxSizeSlices(vector<int>& slices) {
    int n = slices.size() / 3;
    return max(solve(slices, 0, slices.size() - 2, n), solve(slices, 1, slices.size() - 1, n));
}

int main() {
    vector<int> slices = {8, 9, 8, 6, 1, 1};
    cout << maxSizeSlices(slices) << endl;
    return 0;
}

JavaScript

function solve(slices, start, end, n) {
    let prev2 = Array(n + 1).fill(0);
    let prev1 = Array(n + 1).fill(0);

    for (let i = end - start; i >= 0; i--) {
        let current = Array(n + 1).fill(0);
        for (let j = 1; j <= Math.min(n, end - start + 1 - i); j++) {
            current[j] = Math.max(prev1[j], slices[start + i] + prev2[j - 1]);
        }
        prev2 = [...prev1];
        prev1 = [...current];
    }
    return prev1[n];
}

function maxSizeSlices(slices) {
    const n = Math.floor(slices.length / 3);
    return Math.max(solve(slices, 0, slices.length - 2, n), solve(slices, 1, slices.length - 1, n));
}

const slices = [8, 9, 8, 6, 1, 1];
console.log(maxSizeSlices(slices));

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solve(int* slices, int start, int end, int n) {
    int len = end - start + 1;
    int prev2[501] = { 0 };
    int prev1[501] = { 0 };
    for (int i = len - 1; i >= 0; --i) {
        int current[501] = { 0 };
        int maxSlices = max(0, len - 1 - i);
        for (int j = 1; j <= maxSlices && j <= n; ++j) {
            current[j] = max(prev1[j], slices[start + i] + prev2[j - 1]);
        }
        for (int k = 0; k <= n; ++k) {
            prev2[k] = prev1[k];
            prev1[k] = current[k];
        }
    }
    return prev1[n];
}

int maxSizeSlices(int* slices, int slicesSize) {
    int n = slicesSize / 3;
    return max(solve(slices, 0, slicesSize - 2, n), solve(slices, 1, slicesSize - 1, n));
}

int main() {
    int slices[] = {8, 9, 8, 6, 1, 1};
    int size = sizeof(slices) / sizeof(slices[0]);
    printf("%d", maxSizeSlices(slices, size));
    return 0;
}

using System;

class MaxSizeSlicesOptimized {
    int Solve(int[] slices, int start, int end, int n) {
        int len = end - start + 1;
        int[] prev2 = new int[n + 1];
        int[] prev1 = new int[n + 1];

        for (int i = len - 1; i >= 0; i--) {
            int[] current = new int[n + 1];
            for (int j = 1; j <= Math.Min(n, len - i); j++) {
                current[j] = Math.Max(prev1[j], slices[start + i] + prev2[j - 1]);
            }
            prev2 = prev1;
            prev1 = current;
        }

        return prev1[n];
    }

    public int MaxSizeSlices(int[] slices) {
        int n = slices.Length / 3;
        return Math.Max(Solve(slices, 0, slices.Length - 2, n), Solve(slices, 1, slices.Length - 1, n));
    }

    static void Main(string[] args) {
        int[] slices = {8, 9, 8, 6, 1, 1};
        MaxSizeSlicesOptimized solution = new MaxSizeSlicesOptimized();
        Console.WriteLine(solution.MaxSizeSlices(slices));
    }
}

The Python solution keeps track of only two previous state arrays, reducing memory usage while ensuring an optimal solution using dynamic programming.

Complexity

Time Complexity: O(n^2), Space Complexity: O(n), where n is the number of slices.

Try this approach in the editor

Approach 3: Dynamic Programming

We can transform this problem into: In a circular array of length 3n, select n non-adjacent numbers so that the sum of these n numbers is maximized.

The proof is as follows:

When n = 1, we can choose any number in the array.
When n > 1, there must exist a number such that there are two consecutive numbers on one side of it that have not been selected, and at least one number on the other side has not been selected. Therefore, we can remove this number and the numbers on both sides of it from the array, and then the remaining 3(n - 1) numbers form a new circular array. The problem scale is reduced to selecting n - 1 non-adjacent numbers in a circular array of length 3(n - 1), so that the sum of these n - 1 numbers is maximized.

Therefore, the problem we need to solve can be transformed into: In a circular array of length 3n, select n non-adjacent numbers so that the sum of these n numbers is maximized.

In a circular array, if the first number is selected, the last number cannot be selected. If the last number is selected, the first number cannot be selected. Therefore, we can split the circular array into two arrays, one is without the first number, and the other is without the last number. Then solve the maximum value of these two arrays separately, and finally take the larger of the two maximum values.

We use a function g(nums), which represents the maximum sum of selecting n non-adjacent numbers in the array nums. Then our goal is to find the larger value between g(slices) and g(slices[1:]).

The solution method of function g(nums) is as follows:

We denote the length of array nums as m, and define f[i][j] as the maximum sum of selecting j non-adjacent numbers in the first i numbers of array nums.

Consider f[i][j], if we do not select the i-th number, then f[i][j] = f[i - 1][j]. If we select the i-th number, then f[i][j] = f[i - 2][j - 1] + nums[i - 1]. Therefore, we can get the state transition equation:

$f[i][j] = max(f[i - 1][j], f[i - 2][j - 1] + nums[i - 1])

Finally, return f[m][n].

The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of the array slices$.

TypeScript

function maxSizeSlices(slices: number[]): number {
    const n = Math.floor(slices.length / 3);
    const g = (nums: number[]): number => {
        const m = nums.length;
        const f: number[][] = Array(m + 1)
            .fill(0)
            .map(() => Array(n + 1).fill(0));
        for (let i = 1; i <= m; ++i) {
            for (let j = 1; j <= n; ++j) {
                f[i][j] = Math.max(f[i - 1][j], (i > 1 ? f[i - 2][j - 1] : 0) + nums[i - 1]);
            }
        }
        return f[m][n];
    };
    const a = g(slices.slice(0, -1));
    const b = g(slices.slice(1));
    return Math.max(a, b);
}

func maxSizeSlices(slices []int) int {
	n := len(slices) / 3
	g := func(nums []int) int {
		m := len(nums)
		f := make([][]int, m+1)
		for i := range f {
			f[i] = make([]int, n+1)
		}
		for i := 1; i <= m; i++ {
			for j := 1; j <= n; j++ {
				f[i][j] = max(f[i-1][j], nums[i-1])
				if i >= 2 {
					f[i][j] = max(f[i][j], f[i-2][j-1]+nums[i-1])
				}
			}
		}
		return f[m][n]
	}
	a, b := g(slices[:len(slices)-1]), g(slices[1:])
	return max(a, b)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Dynamic Programming - Circular Array	Time Complexity: O(n^2), where n is the number of slices. Space Complexity: O(n^2) for the DP table.
Approach 2: Dynamic Programming with Space Optimization	Time Complexity: O(n^2), Space Complexity: O(n), where n is the number of slices.
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming - Circular Array	O(n^2)	O(n^2)	Best for clarity when first implementing the solution and explaining DP state transitions
Dynamic Programming with Space Optimization	O(n^2)	O(n)	Preferred when memory usage matters or when demonstrating advanced DP optimization in interviews

Frequently asked questions

Is Pizza With 3n Slices easy or hard?

Pizza With 3n Slices is categorized as a Hard problem. The challenge comes from combining circular array constraints with dynamic programming that must select exactly n non-adjacent elements while maximizing the sum.

How to solve Pizza With 3n Slices in O(n)?

A true O(n) solution is not known for this problem because the algorithm must evaluate combinations of slices while enforcing the exact n selections and non-adjacency rule. The best practical approach uses dynamic programming with O(n^2) time and can be optimized to O(n) space.

Pizza With 3n Slices Python or Java solution?

Python and Java implementations typically follow the same DP strategy. Convert the circular array into two linear cases, build a DP structure that tracks selections, and compute the maximum sum. FleetCode provides implementations in Python, Java, C++, C#, JavaScript, and C.

What is the best approach for Pizza With 3n Slices?

The best approach uses dynamic programming with a circular array transformation. Since the first and last slices are adjacent, the problem is split into two linear cases and solved with DP that selects exactly n non-adjacent slices. The final answer is the maximum result from both cases with O(n^2) time complexity.

What data structure is used in Pizza With 3n Slices?

The primary data structure is a dynamic programming table or rolling DP arrays. The input itself is processed as an array, and the algorithm tracks states representing the maximum sum when selecting a certain number of slices without choosing adjacent ones.

What is the time complexity of Pizza With 3n Slices?

The optimal solution runs in O(n^2) time where n represents the number of slices chosen (the array length is 3n). The DP iterates over slices and selection counts. Space complexity is O(n^2) for the full DP table or O(n) with space optimization.

Is Pizza With 3n Slices asked at Google, Amazon, or Meta?

Pizza With 3n Slices represents a classic dynamic programming interview pattern involving circular arrays and constrained selections. Variations of this problem or similar DP optimization questions appear in interviews at companies like Google, Amazon, and Meta.

Pizza With 3n Slices solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dynamic Programming - Circular Array

Approach 2: Approach 2: Dynamic Programming with Space Optimization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Pizza With 3n Slices solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dynamic Programming - Circular Array

Approach 2: Approach 2: Dynamic Programming with Space Optimization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems