Pizza With 3n Slices

Hard
1509.

Pizza With 3n Slices

Pizza With 3n Slices is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon and Google interviews.

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.length
  • 1 <= slices.length <= 500
  • 1 <= slices[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} slices
 * @return {number}
 */
var maxSizeSlices = function(slices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 1 <= slices.length <= 500
  • 1 <= slices[i] <= 1000

Hints for Pizza With 3n Slices

  1. Hint 1

    Which sets of n slices can you end up with? Your slices are never adjacent on the original circle — and in fact every set of n pairwise non-adjacent slices is achievable.

  2. Hint 2

    So the task is: choose exactly n non-adjacent slices on a circle of 3n with maximum total. The circle only adds one constraint — the first and last slice cannot both be chosen.

  3. 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]) picks j non-adjacent slices among the first i.

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

  1. Let n = len(slices) / 3.
  2. Define best(line): dp[i][j] = the largest total of j non-adjacent elements among the first i of line, with dp[i][0] = 0 and impossible states at minus infinity.
  3. dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + line[i-1]) — skip element i, or take it and skip its left neighbour.
  4. The answer is max(best(slices without the last), best(slices without the first)), each asking for exactly n elements.

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 n slices, 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