3219. Minimum Cost for Cutting Cake II - Solution

Q: Is Minimum Cost for Cutting Cake II easy or hard?

Minimum Cost for Cutting Cake II is labeled Hard because identifying the greedy rule is not immediately obvious. Once the insight is recognized, the implementation is straightforward with sorting and simple counters.

Q: Minimum Cost for Cutting Cake II Python/Java solution

Implement the greedy approach by sorting both cost arrays in descending order. Iterate through them while tracking horizontal and vertical segment counts and add cost multiplied by the opposite segment count. The same logic translates directly to Python, Java, C++, C#, JavaScript, and C.

Q: How to solve Minimum Cost for Cutting Cake II in O(n)?

An exact O(n) solution is generally not used because the greedy strategy requires ordering the cuts by cost. Sorting the horizontal and vertical arrays leads to O((m+n) log(m+n)) complexity, which is considered optimal for this problem. After sorting, the remaining computation is a linear pass.

Q: What is the best approach for Minimum Cost for Cutting Cake II?

The optimal solution uses a greedy strategy combined with sorting. Sort horizontal and vertical cut costs in descending order and always apply the largest remaining cut first. Multiply the cost by the number of segments in the opposite direction, then update the segment count. This minimizes how often large costs get multiplied by large segment counts.

Q: Is Minimum Cost for Cutting Cake II asked at Google/Amazon/Meta?

Greedy cost‑minimization problems similar to Minimum Cost for Cutting Cake II appear in interviews at companies like Amazon, Google, and Meta. The pattern of sorting costs and applying the largest operations first is a common greedy interview technique.

Q: What data structure is used in Minimum Cost for Cutting Cake II?

The solution primarily uses arrays along with sorting. Two pointers or indices iterate through the sorted horizontal and vertical cost arrays while counters track how many segments exist in each direction.

Q: What is the time complexity of Minimum Cost for Cutting Cake II?

The optimal greedy solution runs in O((m+n) log(m+n)) time because both cost arrays must be sorted. After sorting, a single linear pass merges the decisions for horizontal and vertical cuts. Space complexity is O(1) aside from the sorting overhead.

The 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.

Example 1:

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

Output: 13

Explanation:

Perform a cut on the vertical line 0 with cost 5, current total cost is 5.
Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.
Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.
Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.
Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.

The total cost is 5 + 1 + 1 + 3 + 3 = 13.

Example 2:

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

Output: 15

Explanation:

Perform a cut on the horizontal line 0 with cost 7.
Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.
Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.

The total cost is 7 + 4 + 4 = 15.

Constraints:

1 <= m, n <= 10⁵
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 <= horizontalCut[i], verticalCut[i] <= 10³

Approach overview

Problem Overview: You are given the costs of horizontal and vertical cuts required to divide a cake into smaller pieces. Each cut cost multiplies by the number of existing segments in the perpendicular direction, so the order of cuts directly affects the total price. The task is to choose a sequence of cuts that minimizes the final cost.

Approach 1: Brute Force Order Simulation (Exponential Time)

The most straightforward idea is to try every possible ordering of horizontal and vertical cuts and compute the total cost for each sequence. At each step you simulate the cut and multiply its cost by the current number of segments in the opposite direction. This works because the pricing rule is deterministic, but the number of permutations grows extremely fast as cuts increase. Time complexity becomes O((m+n)!) with O(1) extra space, which is impractical even for moderate inputs.

Approach 2: Greedy Approach Using Sorting (O((m+n) log(m+n)))

The optimal strategy comes from a greedy observation: expensive cuts should be applied earlier when they are multiplied by fewer segments. If you delay a high‑cost cut, it will be multiplied by a larger segment count later and increase the total cost. Sort both horizontal and vertical cost arrays in descending order and always pick the largest remaining cut.

Track two counters: the number of horizontal pieces and vertical pieces currently formed. When applying a horizontal cut, multiply its cost by the current vertical segment count; when applying a vertical cut, multiply its cost by the horizontal segment count. After applying a cut, increment the corresponding segment counter. Continue merging the two sorted lists similar to a greedy merge process.

This approach ensures expensive operations are applied when multipliers are minimal. Sorting dominates the runtime with O((m+n) log(m+n)) time and the algorithm uses O(1) extra space aside from sorting overhead.

Recommended for interviews: Interviewers expect the greedy insight. Recognizing that larger costs should be applied earlier shows strong problem‑solving intuition with greedy algorithms. Implementation is straightforward once the arrays are sorted using concepts from sorting and simple iteration over arrays. Mentioning the brute force ordering first demonstrates understanding of why the greedy rule is necessary.

Approach 1: Greedy Approach Using Sorting

The problem can be tackled using a greedy approach where we focus on making the most expensive cuts first. This is because a more expensive cut will affect a larger number of subdivisions if made earlier, reducing its overall influence when made later.

Steps:

Sort the horizontal and vertical cuts in descending order.
Use two pointers to traverse through both arrays while choosing the cut with the higher cost, and calculate the current number of partitions affected by the cut to derive the cost impact.
This process involves maintaining and updating the count of horizontal and vertical partitions.

Python

def minCostToCutCake(m, n, horizontalCut, verticalCut):
    horizontalCut.sort(reverse=True)
    verticalCut.sort(reverse=True)
    
    horizontalPieces = 1
    verticalPieces = 1
    totalCost = 0
    
    i = j = 0

    while i < len(horizontalCut) and j < len(verticalCut):
        if horizontalCut[i] > verticalCut[j]:
            totalCost += horizontalCut[i] * verticalPieces
            horizontalPieces += 1
            i += 1
        else:
            totalCost += verticalCut[j] * horizontalPieces
            verticalPieces += 1
            j += 1

    while i < len(horizontalCut):
        totalCost += horizontalCut[i] * verticalPieces
        i += 1
    while j < len(verticalCut):
        totalCost += verticalCut[j] * horizontalPieces
        j += 1

    return totalCost

m = 3
n = 2
horizontalCut = [1, 3]
verticalCut = [5]
print('Total minimum cost:', minCostToCutCake(m, n, horizontalCut, verticalCut))

Java

import java.util.Arrays;
import java.util.Collections;

public class CakeCutting {

    public static int minCostToCutCake(int m, int n, Integer[] horizontalCut, Integer[] verticalCut) {
        Arrays.sort(horizontalCut, Collections.reverseOrder());
        Arrays.sort(verticalCut, Collections.reverseOrder());

        int horizontalPieces = 1, verticalPieces = 1;
        int totalCost = 0;
        int i = 0, j = 0;

        while (i < horizontalCut.length && j < verticalCut.length) {
            if (horizontalCut[i] > verticalCut[j]) {
                totalCost += horizontalCut[i] * verticalPieces;
                horizontalPieces++;
                i++;
            } else {
                totalCost += verticalCut[j] * horizontalPieces;
                verticalPieces++;
                j++;
            }
        }

        while (i < horizontalCut.length) {
            totalCost += horizontalCut[i] * verticalPieces;
            i++;
        }
        while (j < verticalCut.length) {
            totalCost += verticalCut[j] * horizontalPieces;
            j++;
        }

        return totalCost;
    }

    public static void main(String[] args) {
        Integer[] horizontalCut = {1, 3};
        Integer[] verticalCut = {5};
        int m = 3, n = 2;
        int result = minCostToCutCake(m, n, horizontalCut, verticalCut);
        System.out.println("Total minimum cost: " + result);
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int minCostToCutCake(int m, int n, std::vector<int>& horizontalCut, std::vector<int>& verticalCut) {
    std::sort(horizontalCut.begin(), horizontalCut.end(), std::greater<int>());
    std::sort(verticalCut.begin(), verticalCut.end(), std::greater<int>());

    int horizontalPieces = 1, verticalPieces = 1;
    int totalCost = 0;
    int i = 0, j = 0;

    while (i < horizontalCut.size() && j < verticalCut.size()) {
        if (horizontalCut[i] > verticalCut[j]) {
            totalCost += horizontalCut[i] * verticalPieces;
            ++horizontalPieces;
            ++i;
        } else {
            totalCost += verticalCut[j] * horizontalPieces;
            ++verticalPieces;
            ++j;
        }
    }
    while (i < horizontalCut.size()) {
        totalCost += horizontalCut[i] * verticalPieces;
        ++i;
    }
    while (j < verticalCut.size()) {
        totalCost += verticalCut[j] * horizontalPieces;
        ++j;
    }

    return totalCost;
}

int main() {
    std::vector<int> horizontalCut = {1, 3};
    std::vector<int> verticalCut = {5};
    int m = 3, n = 2;
    int result = minCostToCutCake(m, n, horizontalCut, verticalCut);
    std::cout << "Total minimum cost: " << result << std::endl;
    return 0;
}

JavaScript

function minCostToCutCake(m, n, horizontalCut, verticalCut) {
    horizontalCut.sort((a, b) => b - a);
    verticalCut.sort((a, b) => b - a);

    let horizontalPieces = 1;
    let verticalPieces = 1;
    let totalCost = 0;

    let i = 0, j = 0;

    while (i < horizontalCut.length && j < verticalCut.length) {
        if (horizontalCut[i] > verticalCut[j]) {
            totalCost += horizontalCut[i] * verticalPieces;
            horizontalPieces++;
            i++;
        } else {
            totalCost += verticalCut[j] * horizontalPieces;
            verticalPieces++;
            j++;
        }
    }

    while (i < horizontalCut.length) {
        totalCost += horizontalCut[i] * verticalPieces;
        i++;
    }

    while (j < verticalCut.length) {
        totalCost += verticalCut[j] * horizontalPieces;
        j++;
    }

    return totalCost;
}

var horizontalCut = [1, 3];
var verticalCut = [5];
var m = 3, n = 2;
console.log('Total minimum cost:', minCostToCutCake(m, n, horizontalCut, verticalCut));

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

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int minCostToCutCake(int m, int n, int* horizontalCut, int* verticalCut) {
    qsort(horizontalCut, m - 1, sizeof(int), compare);
    qsort(verticalCut, n - 1, sizeof(int), compare);

    int i = 0, j = 0;
    int horizontalPieces = 1, verticalPieces = 1;
    int totalCost = 0;

    while (i < m - 1 && j < n - 1) {
        if (horizontalCut[i] > verticalCut[j]) {
            totalCost += horizontalCut[i] * verticalPieces;
            horizontalPieces++;
            i++;
        } else {
            totalCost += verticalCut[j] * horizontalPieces;
            verticalPieces++;
            j++;
        }
    }
    while (i < m - 1) {
        totalCost += horizontalCut[i] * verticalPieces;
        i++;
    }
    while (j < n - 1) {
        totalCost += verticalCut[j] * horizontalPieces;
        j++;
    }

    return totalCost;
}

int main() {
    int m = 3, n = 2;
    int horizontalCut[] = {1, 3};
    int verticalCut[] = {5};
    int result = minCostToCutCake(m, n, horizontalCut, verticalCut);
    printf("Total minimum cost: %d\n", result);
    return 0;
}

using System;

class CakeCutting {
    static int MinCostToCutCake(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Array.Sort(horizontalCut, (a, b) => b.CompareTo(a));
        Array.Sort(verticalCut, (a, b) => b.CompareTo(a));

        int horizontalPieces = 1, verticalPieces = 1;
        int totalCost = 0;
        int i = 0, j = 0;

        while (i < horizontalCut.Length && j < verticalCut.Length) {
            if (horizontalCut[i] > verticalCut[j]) {
                totalCost += horizontalCut[i] * verticalPieces;
                horizontalPieces++;
                i++;
            } else {
                totalCost += verticalCut[j] * horizontalPieces;
                verticalPieces++;
                j++;
            }
        }

        while (i < horizontalCut.Length) {
            totalCost += horizontalCut[i] * verticalPieces;
            i++;
        }

        while (j < verticalCut.Length) {
            totalCost += verticalCut[j] * horizontalPieces;
            j++;
        }

        return totalCost;
    }

    static void Main() {
        int[] horizontalCut = { 1, 3 };
        int[] verticalCut = { 5 };
        int m = 3, n = 2;
        int result = MinCostToCutCake(m, n, horizontalCut, verticalCut);
        Console.WriteLine("Total minimum cost: " + result);
    }
}

The Python solution makes use of the built-in sort() method with reverse=True to sort in descending order. Then it iteratively calculates the minimum cost by preferring the higher cost cuts first.

Complexity

Time Complexity: O((m + n) log(max(m,n))) due to sorting.
Space Complexity: O(1), with only essential variables for tracking.

Try this approach in the editor

Approach 2: Greedy + Two Pointers

For a given position, the earlier you cut, the fewer cuts are needed, so it is clear that positions with higher costs should be cut earlier.

Therefore, we can sort the arrays horizontalCut and verticalCut in descending order, and then use two pointers i and j to point to the costs in horizontalCut and verticalCut, respectively. Each time, we choose the position with the larger cost to cut, while updating the corresponding number of rows and columns.

Each time a horizontal cut is made, if the number of columns before the cut was v, then the cost of this cut is horizontalCut[i] times v, and then the number of rows h is incremented by one; similarly, each time a vertical cut is made, if the number of rows before the cut was h, then the cost of this cut is verticalCut[j] times h, and then the number of columns v is incremented by one.

Finally, when both i and j reach the end, return the total cost.

The time complexity is O(m times log m + n times log n), and the space complexity is O(log m + log n). Here, m and n are the lengths of horizontalCut and verticalCut, respectively.

TypeScript

function minimumCost(m: number, n: number, horizontalCut: number[], verticalCut: number[]): number {
    horizontalCut.sort((a, b) => b - a);
    verticalCut.sort((a, b) => b - a);
    let ans = 0;
    let [i, j] = [0, 0];
    let [h, v] = [1, 1];
    while (i < m - 1 || j < n - 1) {
        if (j === n - 1 || (i < m - 1 && horizontalCut[i] > verticalCut[j])) {
            ans += horizontalCut[i] * v;
            h++;
            i++;
        } else {
            ans += verticalCut[j] * h;
            v++;
            j++;
        }
    }
    return ans;
}

func minimumCost(m int, n int, horizontalCut []int, verticalCut []int) (ans int64) {
	sort.Sort(sort.Reverse(sort.IntSlice(horizontalCut)))
	sort.Sort(sort.Reverse(sort.IntSlice(verticalCut)))
	i, j := 0, 0
	h, v := 1, 1
	for i < m-1 || j < n-1 {
		if j == n-1 || (i < m-1 && horizontalCut[i] > verticalCut[j]) {
			ans += int64(horizontalCut[i] * v)
			h++
			i++
		} else {
			ans += int64(verticalCut[j] * h)
			v++
			j++
		}
	}
	return
}

Rust

impl Solution {
    pub fn minimum_cost(m: i32, n: i32, mut horizontal_cut: Vec<i32>, mut vertical_cut: Vec<i32>) -> i64 {
        horizontal_cut.sort();
        vertical_cut.sort();
        let (mut i, mut j) = ((m - 2) as isize, (n - 2) as isize);
        let (mut h, mut v) = (1_i64, 1_i64);
        let mut ans: i64 = 0;

        while i >= 0 || j >= 0 {
            if j < 0 || (i >= 0 && horizontal_cut[i as usize] > vertical_cut[j as usize]) {
                ans += horizontal_cut[i as usize] as i64 * v;
                i -= 1;
                h += 1;
            } else {
                ans += vertical_cut[j as usize] as i64 * h;
                j -= 1;
                v += 1;
            }
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach Using Sorting	Time Complexity: O((m + n) log(max(m,n))) due to sorting. Space Complexity: O(1), with only essential variables for tracking.
Greedy + Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Cut Ordering	O((m+n)!)	O(1)	Conceptual understanding of how cut order affects total cost
Greedy with Sorting	O((m+n) log(m+n))	O(1)	Optimal solution for large inputs; choose highest cost cut first

Frequently asked questions

Is Minimum Cost for Cutting Cake II easy or hard?

Minimum Cost for Cutting Cake II is labeled Hard because identifying the greedy rule is not immediately obvious. Once the insight is recognized, the implementation is straightforward with sorting and simple counters.

Minimum Cost for Cutting Cake II Python/Java solution

Implement the greedy approach by sorting both cost arrays in descending order. Iterate through them while tracking horizontal and vertical segment counts and add cost multiplied by the opposite segment count. The same logic translates directly to Python, Java, C++, C#, JavaScript, and C.

How to solve Minimum Cost for Cutting Cake II in O(n)?

An exact O(n) solution is generally not used because the greedy strategy requires ordering the cuts by cost. Sorting the horizontal and vertical arrays leads to O((m+n) log(m+n)) complexity, which is considered optimal for this problem. After sorting, the remaining computation is a linear pass.

What is the best approach for Minimum Cost for Cutting Cake II?

The optimal solution uses a greedy strategy combined with sorting. Sort horizontal and vertical cut costs in descending order and always apply the largest remaining cut first. Multiply the cost by the number of segments in the opposite direction, then update the segment count. This minimizes how often large costs get multiplied by large segment counts.

Is Minimum Cost for Cutting Cake II asked at Google/Amazon/Meta?

Greedy cost‑minimization problems similar to Minimum Cost for Cutting Cake II appear in interviews at companies like Amazon, Google, and Meta. The pattern of sorting costs and applying the largest operations first is a common greedy interview technique.

What data structure is used in Minimum Cost for Cutting Cake II?

The solution primarily uses arrays along with sorting. Two pointers or indices iterate through the sorted horizontal and vertical cost arrays while counters track how many segments exist in each direction.

What is the time complexity of Minimum Cost for Cutting Cake II?

The optimal greedy solution runs in O((m+n) log(m+n)) time because both cost arrays must be sorted. After sorting, a single linear pass merges the decisions for horizontal and vertical cuts. Space complexity is O(1) aside from the sorting overhead.

Minimum Cost for Cutting Cake II solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Sorting

Approach 2: Greedy + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Cost for Cutting Cake II solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach Using Sorting

Approach 2: Greedy + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems