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 <= 20horizontalCut.length == m - 1verticalCut.length == n - 11 <= horizontalCut[i], verticalCut[i] <= 103Problem Overview: You are given the costs of horizontal and vertical cuts needed to divide an m x n cake into 1x1 pieces. Each time you perform a cut, the cost is multiplied by the number of current segments in the opposite direction. The goal is to choose the order of cuts so the total cost is minimized.
Approach 1: Greedy with Priority Queue (O((m+n) log(m+n)) time, O(m+n) space)
The key observation: expensive cuts should be applied as early as possible. When you perform a cut later, it gets multiplied by more segments, which increases its total cost. To minimize the final sum, always perform the highest-cost cut first. Push all horizontal and vertical cuts into a max heap (priority queue) and repeatedly extract the largest cost. Maintain counters for horizontal and vertical segments. A horizontal cut contributes cost * verticalSegments, while a vertical cut contributes cost * horizontalSegments. This greedy strategy guarantees the minimum cost because it prevents expensive cuts from being multiplied by larger segment counts later.
This approach relies heavily on ideas from Greedy algorithms and works well because the cost contribution grows multiplicatively as segments increase.
Approach 2: Greedy with Sorting (O((m+n) log(m+n)) time, O(1) extra space)
Instead of using a heap, you can sort both cost arrays in descending order and simulate the greedy selection using two pointers. Compare the next largest horizontal and vertical cost and pick the larger one. Update the segment counters accordingly and accumulate the weighted cost. Sorting allows you to process cuts in decreasing order without maintaining a heap, making the implementation simpler while keeping the same asymptotic complexity.
This version primarily uses Array manipulation and Sorting. In practice it runs slightly faster due to lower constant factors compared to a priority queue.
Approach 3: Dynamic Programming (O(h * v) time, O(h * v) space)
A Dynamic Programming formulation considers how many horizontal and vertical cuts have already been performed. Let dp[i][j] represent the minimum cost after performing i horizontal and j vertical cuts. The next operation can either be another horizontal cut or a vertical cut. A horizontal cut adds horizontalCost[i] * (j + 1), while a vertical cut adds verticalCost[j] * (i + 1). Transition between states until all cuts are used. This explicitly explores interleavings of cut orders but is slower and uses more memory than the greedy strategy.
Recommended for interviews: The greedy strategy with sorting or a priority queue is the expected solution. It demonstrates the core insight: performing higher-cost cuts earlier prevents them from being multiplied by larger segment counts. Mentioning the DP formulation shows deeper understanding, but implementing the greedy approach efficiently is what interviewers typically look for.
The key idea is to prioritize cuts with higher costs first, as these influence the subsequential cutting costs significantly. We use a priority queue (or max heap) to always perform the cut with the maximum cost from both available horizontal and vertical cuts. This ensures that more expensive cuts are counted first while there are more pieces to divide the cake into.
This solution starts by sorting both the horizontal and vertical cut arrays in descending order. It maintains counters for horizontal pieces and vertical pieces. Then, using a greedy strategy, it determines whether it should cut horizontally or vertically by selecting the maximum available cost cut. The total cost is accumulated by the number of pieces influenced by the cut. The iteration continues until all cuts are made, ensuring it checks both remaining horizontal and vertical cuts if one is exhausted first. This method efficiently calculates the minimum possible cost.
Time Complexity: O((m + n) log(m + n)) due to the sorting step. Space complexity: O(1) since it uses only a fixed amount of extra space.
In the dynamic programming approach, we define a 2D DP array where dp[i][j] represents the minimal cost to cut the i x j subgrid into 1 x 1 pieces. This approach utilizes memoization to store previously calculated results efficiently. It systematically builds the solution by evaluating subproblems and their optimal solutions.
This DP-based solution defines a state dp[i][j] where i x j is the cost to split the cake to 1x1 segments. By evaluating and combining each row and column cut efficiently, it determines the cumulative minimal cost. It recursively breaks down the problem while memoizing results to avoid re-computation.
Time Complexity: O(m * n), Space complexity: O(m * n).
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: Priority Queue | Time Complexity: O((m + n) log(m + n)) due to the sorting step. Space complexity: O(1) since it uses only a fixed amount of extra space. |
| Dynamic Programming Approach | Time Complexity: O(m * n), Space complexity: O(m * n). |
| Greedy + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Priority Queue | O((m+n) log(m+n)) | O(m+n) | When you want a straightforward greedy implementation that always selects the largest remaining cut. |
| Greedy with Sorting | O((m+n) log(m+n)) | O(1) | Most common interview solution; simpler and faster than heap-based implementation. |
| Dynamic Programming | O(h * v) | O(h * v) | Useful for understanding all possible cut orders or when demonstrating DP reasoning. |
Minimum Cost for Cutting Cake I & II | Thought Process | Leetcode 3218 | 3219 | codestorywithMIK • codestorywithMIK • 5,654 views views
Watch 8 more video solutions →Practice Minimum Cost for Cutting Cake I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor