Pizza With 3n Slices — Solution in Python, Java & C++
Pizza With 3n Slices solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Pizza With 3n Slices is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Greedy, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A round pizza is cut into 3n slices of different sizes, listed clockwise in slices. You share it with two friends, Alice and Bob, and the slices are taken in rounds:
- You pick any remaining slice.
- Alice takes the next remaining slice counter-clockwise from yours.
- Bob takes the next remaining slice clockwise from yours.
Rounds repeat until no slices are left. Return the maximum total size of the slices you can end up with.
Example 1
Input: slices = [5,1,1,5,1,1]
Output: 10
Explanation: Pick a 5; Alice and Bob take the 1s beside it. The other 5 is still there in the second round.
Example 2
Input: slices = [3,7,2]
Output: 7
Example 3
Input: slices = [4,1,2,5,8,3,1,9,7]
Output: 21
Explanation: The slices of size 4, 8 and 9 — no two of them are next to each other.
Constraints
3 * n == slices.length1 <= slices.length <= 5001 <= slices[i] <= 1000
Hints for Pizza With 3n Slices
Hint 1
Which sets of
nslices can you end up with? Your slices are never adjacent on the original circle — and in fact every set ofnpairwise non-adjacent slices is achievable.Hint 2
So the task is: choose exactly
nnon-adjacent slices on a circle of3nwith maximum total. The circle only adds one constraint — the first and last slice cannot both be chosen.Hint 3
Break the circle twice: solve the line without the last slice and the line without the first slice. On a line,
dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + slices[i])picksjnon-adjacent slices among the firsti.
How to solve Pizza With 3n Slices
The game is a disguise. Every round removes your slice and its two current neighbours, so your slices are pairwise non-adjacent on the original circle; conversely any n pairwise non-adjacent slices out of 3n can be collected in some order (always pick a chosen slice that has an unchosen slice on both sides next to it — one exists while the circle is at least three times the number of picks left). The problem becomes: pick n non-adjacent elements of a circular array with maximum sum.
Approach
- Let
n = len(slices) / 3. - Define
best(line):dp[i][j]= the largest total ofjnon-adjacent elements among the firstiofline, withdp[i][0] = 0and impossible states at minus infinity. dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + line[i-1])— skip elementi, or take it and skip its left neighbour.- The answer is
max(best(slices without the last), best(slices without the first)), each asking for exactlynelements.
Why it works
On the circle the only extra constraint versus a line is that the first and last slices are neighbours. Any valid selection leaves out at least one of them, so it is a valid selection of one of the two lines; and every valid selection of either line is valid on the circle. Taking the better of the two line answers therefore gives the circular optimum, and the line DP is the standard take-or-skip recurrence.
Complexity
- Time —
O(n^2) - Space —
O(n^2)
Pitfalls
- Choose exactly
nslices, not 'as many as you like' — the count is part of the DP state. - Remember the wrap-around: the first and last slices are adjacent.
- A plain greedy (always take the largest slice) fails — taking it can block two medium slices worth more.
Reference solution
Python
from typing import List
def maxSizeSlices(slices: List[int]) -> int:
m = len(slices) // 3
NEG = -10 ** 9
def best(line):
L = len(line)
dp = [[NEG] * (m + 1) for _ in range(L + 1)]
for i in range(L + 1):
dp[i][0] = 0
for i in range(1, L + 1):
for j in range(1, m + 1):
before = dp[i - 2][j - 1] if i >= 2 else (0 if j == 1 else NEG)
dp[i][j] = max(dp[i - 1][j], before + line[i - 1])
return dp[L][m]
return max(best(slices[:-1]), best(slices[1:]))Java
static int bestNonAdjacent(int[] slices, int lo, int hi, int m) {
final int NEG = -1000000000;
int L = hi - lo;
int[][] dp = new int[L + 1][m + 1];
for (int i = 0; i <= L; i++) {
Arrays.fill(dp[i], NEG);
dp[i][0] = 0;
}
for (int i = 1; i <= L; i++) {
for (int j = 1; j <= m; j++) {
int before = i >= 2 ? dp[i - 2][j - 1] : (j == 1 ? 0 : NEG);
dp[i][j] = Math.max(dp[i - 1][j], before + slices[lo + i - 1]);
}
}
return dp[L][m];
}
public static int maxSizeSlices(int[] slices) {
int n = slices.length, m = n / 3;
return Math.max(bestNonAdjacent(slices, 0, n - 1, m), bestNonAdjacent(slices, 1, n, m));
}C++
int bestNonAdjacent(const vector<int>& slices, int lo, int hi, int m) {
const int NEG = -1000000000;
int L = hi - lo;
vector<vector<int>> dp(L + 1, vector<int>(m + 1, NEG));
for (int i = 0; i <= L; i++) dp[i][0] = 0;
for (int i = 1; i <= L; i++) {
for (int j = 1; j <= m; j++) {
int before = i >= 2 ? dp[i - 2][j - 1] : (j == 1 ? 0 : NEG);
dp[i][j] = max(dp[i - 1][j], before + slices[lo + i - 1]);
}
}
return dp[L][m];
}
int maxSizeSlices(vector<int>& slices) {
int n = slices.size(), m = n / 3;
return max(bestNonAdjacent(slices, 0, n - 1, m), bestNonAdjacent(slices, 1, n, m));
}JavaScript
var maxSizeSlices = function(slices) {
var m = slices.length / 3, NEG = -1e9;
var best = function(lo, hi) {
var L = hi - lo;
var dp = [];
for (var i = 0; i <= L; i++) {
var row = new Array(m + 1).fill(NEG);
row[0] = 0;
dp.push(row);
}
for (var i = 1; i <= L; i++) {
for (var j = 1; j <= m; j++) {
var before = i >= 2 ? dp[i - 2][j - 1] : (j === 1 ? 0 : NEG);
dp[i][j] = Math.max(dp[i - 1][j], before + slices[lo + i - 1]);
}
}
return dp[L][m];
};
var n = slices.length;
return Math.max(best(0, n - 1), best(1, n));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming