Skip to main content
Talentd

Minimum Cost for Cutting Cake II - Solution & Explanation

HardArrayGreedySorting20 min readAsked at: Google
Practice this problem

Problem Statement

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:

  1. Cut along a horizontal line i at a cost of horizontalCut[i].
  2. 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 <= 105
  • horizontalCut.length == m - 1
  • verticalCut.length == n - 1
  • 1 <= horizontalCut[i], verticalCut[i] <= 103

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:

  1. Sort the horizontal and vertical cuts in descending order.
  2. 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.
  3. This process involves maintaining and updating the count of horizontal and vertical partitions.

The C solution involves sorting the cut arrays and iterating through them to calculate the minimum cost. The qsort function is used to sort the arrays, and a while loop goes through both arrays to calculate the cost based on the partition effects of each cut. The remaining elements are added after one array is exhausted.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O((m + n) log(max(m,n))) due to sorting.
Space Complexity: O(1), as sorting is done in place and only variables are used for calculations.

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach Using Sorting

Time Complexity: O((m + n) log(max(m,n))) due to sorting.
Space Complexity: O(1), as sorting is done in place and only variables are used for calculations.

Greedy + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Cut OrderingO((m+n)!)O(1)Conceptual understanding of how cut order affects total cost
Greedy with SortingO((m+n) log(m+n))O(1)Optimal solution for large inputs; choose highest cost cut first

Video Solution

Minimum Cost for Cutting Cake I & II | Thought Process | Leetcode 3218 | 3219 | codestorywithMIK • codestorywithMIK • 6,017 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Cost for Cutting Cake II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost for Cutting Cake I