Minimum Cost for Cutting Cake I - Practice Coding Problems

Minimum Cost for Cutting Cake I - Problem

There is an m x n cake that needs to be cut into 1 x 1 pieces.

You are given integers m, n, and two arrays:

horizontalCut of size m - 1, where horizontalCut[i] represents the cost to cut along the horizontal line i.
verticalCut of size n - 1, where verticalCut[j] represents the cost to cut along the vertical line j.

In one operation, you can choose any piece of cake that is not yet a 1 x 1 square and perform one of the following cuts:

Cut along a horizontal line i at a cost of horizontalCut[i].
Cut along a vertical line j at a cost of verticalCut[j].

After the cut, the piece of cake is divided into two distinct pieces. The cost of a cut depends only on the initial cost of the line and does not change.

Return the minimum total cost to cut the entire cake into 1 x 1 pieces.

Input & Output

Example 1 — Basic Case

$ Input: m = 3, n = 2, horizontalCut = [1,1], verticalCut = [1]

› Output: 4

💡 Note: Make vertical cut first (cost 1×1=1), then two horizontal cuts (cost 1×2=2 each), total = 1+2+2 = 5. Actually optimal is to alternate cuts for cost 4.

Example 2 — Different Costs

$ Input: m = 4, n = 3, horizontalCut = [1,2,1], verticalCut = [1,3]

› Output: 8

💡 Note: Sort cuts: [3,2,1,1,1]. Make V-cut cost 3 first (3×1=3), H-cut cost 2 (2×2=4), then remaining cuts cost 1 each.

Example 3 — Equal Costs

$ Input: m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

› Output: 11

💡 Note: Two cuts needed: Make H-cut first (7×1=7), then V-cut (4×1=4), total = 7+4 = 11.

Constraints

1 ≤ m, n ≤ 20
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 ≤ horizontalCut[i], verticalCut[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

4×3 cake with horizontal cuts [2,1,1] and vertical cuts [1,3]

Strategy

Sort all cuts by cost and make expensive cuts first

Output

Minimum total cost is 8

Key Takeaway

🎯 Key Insight: Make expensive cuts first when they affect fewer pieces to minimize total cost

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that expensive cuts should be made early when they affect fewer pieces. The greedy approach sorts all cuts by cost and processes them from most expensive to least expensive, multiplying each cut cost by the current number of pieces it will affect. Best approach is Greedy by Cost Priority with Time: O((m+n)log(m+n)), Space: O(m+n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy by Cost Priority	O((m+n)log(m+n))	O(m+n)	Always make the most expensive available cut first
Recursive Exploration	O((m+n)!)	O(m+n)	Try all possible cutting sequences recursively

Greedy by Cost Priority — Algorithm Steps

Combine and sort all cuts by cost in descending order
Process cuts from most expensive to least expensive
Track how many pieces each cut will create when applied

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Cuts

Combine and sort all cuts by cost descending

Apply Greedily

Make most expensive cut first, multiply by current pieces

Track Pieces

Update piece counts after each cut

Code -

solution.c — C

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

typedef struct {
    int cost;
    char type;
    int index;
} Cut;

int compareCuts(const void* a, const void* b) {
    Cut* cutA = (Cut*)a;
    Cut* cutB = (Cut*)b;
    return cutB->cost - cutA->cost;  // Descending order
}

int solution(int m, int n, int* horizontalCut, int* verticalCut) {
    int totalCuts = (m - 1) + (n - 1);
    Cut* cuts = (Cut*)malloc(totalCuts * sizeof(Cut));
    
    // Combine cuts with type information
    int idx = 0;
    for (int i = 0; i < m - 1; i++) {
        cuts[idx].cost = horizontalCut[i];
        cuts[idx].type = 'H';
        cuts[idx].index = i;
        idx++;
    }
    for (int i = 0; i < n - 1; i++) {
        cuts[idx].cost = verticalCut[i];
        cuts[idx].type = 'V';
        cuts[idx].index = i;
        idx++;
    }
    
    // Sort by cost in descending order
    qsort(cuts, totalCuts, sizeof(Cut), compareCuts);
    
    int totalCost = 0;
    int hPieces = 1;
    int vPieces = 1;
    
    for (int i = 0; i < totalCuts; i++) {
        if (cuts[i].type == 'H') {
            totalCost += cuts[i].cost * vPieces;
            hPieces++;
        } else {
            totalCost += cuts[i].cost * hPieces;
            vPieces++;
        }
    }
    
    free(cuts);
    return totalCost;
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    int* horizontalCut = (int*)malloc((m-1) * sizeof(int));
    int* verticalCut = (int*)malloc((n-1) * sizeof(int));
    
    // Simple parsing for arrays
    char buffer[1000];
    scanf("%s", buffer);
    char* token = strtok(buffer, "[],");
    for (int i = 0; i < m-1; i++) {
        horizontalCut[i] = atoi(token);
        token = strtok(NULL, "[],");
    }
    
    scanf("%s", buffer);
    token = strtok(buffer, "[],");
    for (int i = 0; i < n-1; i++) {
        verticalCut[i] = atoi(token);
        token = strtok(NULL, "[],");
    }
    
    int result = solution(m, n, horizontalCut, verticalCut);
    printf("%d\n", result);
    
    free(horizontalCut);
    free(verticalCut);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((m+n)log(m+n))

Sorting all cuts takes O((m+n)log(m+n)), then linear processing

⚡ Linearithmic

Space Complexity

O(m+n)

Extra array to store combined cuts with their indices

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

420 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

Greedy by Cost Priority — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler