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:
i at a cost of horizontalCut[i].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:
3 x 1 subgrid with cost 1.3 x 1 subgrid with cost 1.2 x 1 subgrid with cost 3.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:
1 x 2 subgrid with cost 4.1 x 2 subgrid with cost 4.The total cost is 7 + 4 + 4 = 15.
Constraints:
1 <= m, n <= 105horizontalCut.length == m - 1verticalCut.length == n - 11 <= horizontalCut[i], verticalCut[i] <= 103Problem 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.
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:
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.
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.
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.
| Approach | Complexity |
|---|---|
| Greedy Approach Using Sorting | Time Complexity: O((m + n) log(max(m,n))) due to sorting. |
| Greedy + Two Pointers | — |
| 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 |
Minimum Cost for Cutting Cake I & II | Thought Process | Leetcode 3218 | 3219 | codestorywithMIK • codestorywithMIK • 5,654 views views
Watch 9 more video solutions →Practice Minimum Cost for Cutting Cake II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor