Pizza With 3n Slices - Practice Coding Problems

Pizza With 3n Slices - 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 pizza.

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.

Input & Output

Example 1 — Basic Case

$ Input: slices = [1,2,3,4,5,6]

› Output: 10

💡 Note: Pick slices 3 and 6 for maximum sum. When you pick 3, Alice gets 2, Bob gets 4. When you pick 6, Alice gets 5, Bob gets 1. Total: 3 + 6 = 9. Wait, actually picking slices with values 4 and 6 gives sum 10.

Example 2 — Larger Array

$ Input: slices = [4,1,2,5,8,3,1,9,7]

› Output: 21

💡 Note: With n=3, you need to pick 3 slices. Optimal picks are slices with values 8, 9, and 4, giving sum 8 + 9 + 4 = 21.

Example 3 — Small Array

$ Input: slices = [3,1,2]

› Output: 3

💡 Note: With n=1, you pick 1 slice. The maximum value slice is 3, so pick that one.

Constraints

3 ≤ slices.length ≤ 500
slices.length % 3 == 0
1 ≤ slices[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array of 3n pizza slices

Constraint

Picking slice i blocks slices i-1 and i+1

Goal

Pick n slices to maximize your sum

Key Takeaway

🎯 Key Insight: Convert circular array problem to two linear House Robber problems by excluding first or last element

Asked in

G Google 15 F Facebook 12 a Amazon 8

This problem is equivalent to selecting n non-adjacent elements from a circular array to maximize sum. The key insight is to convert the circular constraint into two linear subproblems. Best approach uses 2D Dynamic Programming with Time: O(n²), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming	O(n²)	O(n²)	Bottom-up DP table where dp[i][j] represents max sum using j slices from first i positions
Brute Force Backtracking	O(2^n)	O(n)	Try all possible ways to pick n slices ensuring no two are adjacent
Memoization (Top-Down DP)	O(n²)	O(n²)	Convert to two linear array problems with memoization to avoid recomputation

2D Dynamic Programming — Algorithm Steps

Create dp[i][j] = max sum with j picks from first i positions
For each position, decide to pick (skip next) or skip current
Fill table bottom-up
Handle circular by excluding first or last element

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create dp table with base cases

Fill

For each cell, max of pick vs skip

Result

dp[m][n] contains optimal answer

Code -

solution.c — C

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

int robLinear(int* arr, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= m; i++) {
        int maxJ = (i / 2 < n) ? i / 2 : n;
        for (int j = 1; j <= maxJ; j++) {
            dp[i][j] = dp[i-1][j];
            if (i >= 2) {
                int pick = dp[i-2][j-1] + arr[i-1];
                if (pick > dp[i][j]) dp[i][j] = pick;
            } else if (j == 1) {
                if (arr[i-1] > dp[i][j]) dp[i][j] = arr[i-1];
            }
        }
    }
    
    return dp[m][n];
}

int solution(int* slices, int len) {
    int n = len / 3;
    
    int case1 = robLinear(slices, len - 1, n);
    int case2 = robLinear(slices + 1, len - 1, n);
    
    return (case1 > case2) ? case1 : case2;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int slices[100];
    int len = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        slices[len++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(slices, len));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two passes of n positions × n picks, each cell computed once

⚠ Quadratic Growth

Space Complexity

O(n²)

2D DP table of size n×n for both linear cases

⚠ Quadratic Space

25.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler