Minimum Cost for Cutting Cake II
HardPrompt
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:
horizontalCutof sizem - 1, wherehorizontalCut[i]represents the cost to cut along the horizontal linei.verticalCutof sizen - 1, whereverticalCut[j]represents the cost to cut along the vertical linej.
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
iat a cost ofhorizontalCut[i]. - Cut along a vertical line
jat a cost ofverticalCut[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 1subgrid with cost 1. - Perform a cut on the horizontal line 0 on
3 x 1subgrid with cost 1. - Perform a cut on the horizontal line 1 on
2 x 1subgrid with cost 3. - Perform a cut on the horizontal line 1 on
2 x 1subgrid 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 2subgrid with cost 4. - Perform a cut on the vertical line 0 on
1 x 2subgrid 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] <= 103
Approaches
3 approaches with complexity analysis and trade-offs.
This approach attempts to solve the problem by exploring every possible sequence of cuts using dynamic programming with bitmasking. A state in our DP is defined by the set of horizontal and vertical cuts that have already been performed. These sets are represented by bitmasks. For each state, we recursively calculate the minimum cost by trying every possible next cut (both horizontal and vertical) and choosing the one that leads to the minimum total cost for the subsequent cuts.
Algorithm
- Define a recursive function
solve(hMask, vMask)with memoization, wherehMaskandvMaskare bitmasks representing the cuts already made. - The base case for the recursion is when all cuts have been made (all bits in masks are set), in which case the cost is 0.
- If the result for a state
(hMask, vMask)is already in the memoization table, return it. - To compute the cost for a state, initialize a
minCostvariable to infinity. - Determine the current number of horizontal and vertical pieces. The number of horizontal pieces is
popcount(hMask) + 1, and vertical pieces ispopcount(vMask) + 1. - Iterate through all horizontal cuts. If a cut
ihas not been made yet, calculate the cost of making it now:cost = horizontalCut[i] * (number of vertical pieces) + solve(new_hMask, vMask). UpdateminCostwith this value if it's smaller. - Similarly, iterate through all vertical cuts. If a cut
jhas not been made, calculate its cost:cost = verticalCut[j] * (number of horizontal pieces) + solve(hMask, new_vMask). UpdateminCostaccordingly. - Store the computed
minCostin the memoization table and return it. - The initial call to the function will be
solve(0, 0).
Walkthrough
The core of this method is a recursive function, let's call it solve(hMask, vMask), which computes the minimum cost to finish cutting the cake given that the cuts represented by hMask (for horizontal) and vMask (for vertical) are already done. The cost of making a new cut depends on the number of pieces it must slice through. A horizontal cut slices through a number of pieces equal to the current number of vertical segments (popcount(vMask) + 1). A vertical cut slices through a number of pieces equal to the current number of horizontal segments (popcount(hMask) + 1). The function explores making each available cut, recursively calls itself for the new state, and takes the minimum over all possibilities. Memoization is used to store the results for each (hMask, vMask) pair to avoid redundant computations. However, due to the 2^(m-1) * 2^(n-1) possible states, this approach is not feasible for the problem's constraints.
// This is a conceptual implementation and will time out for the given constraints.import java.util.Arrays; class Solution { private long[][] memo; private int m, n; private int[] horizontalCut, verticalCut; private int hTargetMask, vTargetMask; public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) { // This approach is too slow for the given constraints but illustrates the concept. if (m > 15 || n > 15) return -1; // Heuristic check to prevent memory errors this.m = m; this.n = n; this.horizontalCut = horizontalCut; this.verticalCut = verticalCut; this.hTargetMask = (1 << (m - 1)) - 1; this.vTargetMask = (1 << (n - 1)) - 1; this.memo = new long[1 << (m - 1)][1 << (n - 1)]; for (long[] row : memo) { Arrays.fill(row, -1); } return solve(0, 0); } private long solve(int hMask, int vMask) { if (hMask == hTargetMask && vMask == vTargetMask) { return 0; } if (memo[hMask][vMask] != -1) { return memo[hMask][vMask]; } long minCost = Long.MAX_VALUE; int hPieces = Integer.bitCount(hMask) + 1; int vPieces = Integer.bitCount(vMask) + 1; // Try making a horizontal cut if (hMask != hTargetMask) { for (int i = 0; i < m - 1; i++) { if ((hMask & (1 << i)) == 0) { long currentCost = (long) horizontalCut[i] * vPieces + solve(hMask | (1 << i), vMask); minCost = Math.min(minCost, currentCost); } } } // Try making a vertical cut if (vMask != vTargetMask) { for (int i = 0; i < n - 1; i++) { if ((vMask & (1 << i)) == 0) { long currentCost = (long) verticalCut[i] * hPieces + solve(hMask, vMask | (1 << i)); minCost = Math.min(minCost, currentCost); } } } return memo[hMask][vMask] = minCost; }}Complexity
Time
O((m+n) * 2^(m+n)). There are `2^(m-1) * 2^(n-1)` states, and for each state, we iterate through up to `m-1 + n-1` possible next cuts.
Space
O(2^(m+n)). The memoization table requires `2^(m-1) * 2^(n-1)` entries.
Trade-offs
Pros
It is a correct approach that is guaranteed to find the optimal solution by exhaustively checking all possibilities.
Cons
Extremely high time and space complexity, making it impractical for the given constraints.
The state space grows exponentially with
mandn, leading to Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) errors for anything but very small inputs.
A more efficient method is a greedy approach. The key insight is that it is always optimal to perform the cut with the highest cost as early as possible. The cost of a cut is its base cost multiplied by the number of pieces it divides. By making expensive cuts when the cake is in fewer pieces, we minimize their contribution to the total cost. This strategy involves combining all cuts, sorting them by cost in descending order, and then processing them one by one.
Algorithm
- Create a custom
Cutclass or a similar structure to hold the cost and type ('H' for horizontal, 'V' for vertical) of each cut. - Create a single list and populate it with all
m-1horizontal cuts andn-1vertical cuts. - Sort this combined list of cuts in descending order based on their cost.
- Initialize
totalCost = 0,hPieces = 1(representing one initial horizontal piece), andvPieces = 1(one initial vertical piece). - Iterate through the sorted list of cuts.
- For each cut:
- If it's a horizontal cut, add
cost * vPiecestototalCostand then incrementhPieces. - If it's a vertical cut, add
cost * hPiecestototalCostand then incrementvPieces.
- If it's a horizontal cut, add
- After iterating through all the cuts,
totalCostwill hold the minimum cost.
Walkthrough
This greedy strategy is based on the observation that the total cost is a sum of terms, where each term is cost_of_cut * number_of_pieces_it_cuts. To minimize this sum, we should pair large costs with small multipliers. The multipliers (hPieces and vPieces) start at 1 and increase as we make more cuts. Therefore, by processing cuts in descending order of their base cost, we ensure that the highest costs are multiplied by the smallest possible multipliers.
To implement this, we can create a helper class, say Cut, to store a cut's cost and its type (horizontal or vertical). We populate a list with all cuts from horizontalCut and verticalCut. Then, we sort this list in descending order of cost. Finally, we iterate through the sorted list, calculating the cost for each cut based on the current number of horizontal and vertical pieces and updating the piece counts.
import java.util.ArrayList;import java.util.List; class Solution { class Cut implements Comparable<Cut> { int cost; char type; // 'H' for horizontal, 'V' for vertical Cut(int cost, char type) { this.cost = cost; this.type = type; } @Override public int compareTo(Cut other) { return Integer.compare(other.cost, this.cost); } } public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) { List<Cut> cuts = new ArrayList<>(); for (int cost : horizontalCut) { cuts.add(new Cut(cost, 'H')); } for (int cost : verticalCut) { cuts.add(new Cut(cost, 'V')); } // Sort cuts in descending order of cost Collections.sort(cuts); long totalCost = 0; long hPieces = 1; long vPieces = 1; for (Cut cut : cuts) { if (cut.type == 'H') { totalCost += (long) cut.cost * vPieces; hPieces++; } else { // type == 'V' totalCost += (long) cut.cost * hPieces; vPieces++; } } return totalCost; }}Complexity
Time
O(N log N), where `N = m + n`. The dominant operation is sorting the combined list of cuts.
Space
O(m+n). We need to create a list to store all `m-1 + n-1` cuts.
Trade-offs
Pros
Finds the optimal solution with a much better time complexity than the DP approach.
The greedy logic is intuitive and relatively straightforward to implement.
Cons
Requires
O(m+n)auxiliary space to store the combined list of cuts.The time complexity, while polynomial, is slightly worse than the most optimal approach due to sorting a larger, combined array.
This is the most efficient approach, building upon the same greedy strategy but with an implementation optimization. Instead of merging the two arrays of cuts into a single large array and then sorting, we can sort the horizontalCut and verticalCut arrays independently. After sorting, we can use a two-pointer technique, similar to the merge step in merge-sort, to pick the highest-cost cut at each step from either of the two arrays.
Algorithm
- Sort both
horizontalCutandverticalCutarrays. For this strategy, it's convenient to sort them in ascending order. - Initialize
totalCost = 0,hPieces = 1, andvPieces = 1. - Initialize two pointers:
hPtrto the end of the sortedhorizontalCutarray (m-2) andvPtrto the end of the sortedverticalCutarray (n-2). These pointers will now point to the cuts with the highest costs. - Loop while either
hPtrorvPtris valid (i.e.,>= 0). - Inside the loop, compare the costs at
horizontalCut[hPtr]andverticalCut[vPtr].- If the horizontal cut cost is greater than the vertical cut cost (or if the vertical pointer is out of bounds), process the horizontal cut. Add
horizontalCut[hPtr] * vPiecestototalCost, incrementhPieces, and decrementhPtr. - Otherwise, process the vertical cut. Add
verticalCut[vPtr] * hPiecestototalCost, incrementvPieces, and decrementvPtr.
- If the horizontal cut cost is greater than the vertical cut cost (or if the vertical pointer is out of bounds), process the horizontal cut. Add
- Continue until both pointers have traversed their respective arrays. The final
totalCostis the minimum cost.
Walkthrough
By sorting both horizontalCut and verticalCut arrays (e.g., in ascending order), we can use pointers starting from the end of each array to access the cuts in descending order of cost. We maintain a pointer for horizontal cuts (hPtr) and one for vertical cuts (vPtr). In each step, we compare the costs at the current pointers and choose the larger one. This simulates iterating through a merged, sorted list of all cuts without actually creating one.
If horizontalCut[hPtr] is greater than verticalCut[vPtr], we 'perform' this horizontal cut. The cost added is horizontalCut[hPtr] * vPieces. We then increment the number of horizontal pieces (hPieces) and move the horizontal pointer (hPtr--). If the vertical cut is more expensive, we do the analogous operations for the vertical cut. This continues until all cuts are processed. This method avoids the O(m+n) space overhead of the previous approach and has a slightly better time complexity constant.
import java.util.Arrays; class Solution { public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) { Arrays.sort(horizontalCut); Arrays.sort(verticalCut); long totalCost = 0; long hPieces = 1; long vPieces = 1; int hPtr = m - 2; // Pointer for horizontalCut, starting from the largest int vPtr = n - 2; // Pointer for verticalCut, starting from the largest while (hPtr >= 0 || vPtr >= 0) { long hCost = (hPtr >= 0) ? horizontalCut[hPtr] : -1; long vCost = (vPtr >= 0) ? verticalCut[vPtr] : -1; if (hCost > vCost) { // Take horizontal cut totalCost += hCost * vPieces; hPieces++; hPtr--; } else { // Take vertical cut totalCost += vCost * hPieces; vPieces++; vPtr--; } } return totalCost; }}Complexity
Time
O(m log m + n log n). This is dominated by the time to sort the two cut arrays. The subsequent two-pointer traversal takes linear time, O(m+n).
Space
O(log m + log n) or O(1). This is the space used by the in-place sorting algorithm (e.g., Quicksort's recursion stack). If we cannot modify the input arrays, it becomes O(m+n) to store copies.
Trade-offs
Pros
Most efficient solution in terms of both time and space complexity.
Avoids the overhead of creating and managing a combined list of cuts.
The time complexity is governed by sorting two smaller arrays instead of one large one, which is faster in practice.
Cons
This approach requires modifying the input arrays by sorting them. If the input arrays are immutable, we would need to create copies, which would increase the space complexity to
O(m+n).
Solutions
Solution
class Solution {public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) { Arrays.sort(horizontalCut); Arrays.sort(verticalCut); long ans = 0; int i = m - 2, j = n - 2; int h = 1, v = 1; while (i >= 0 || j >= 0) { if (j < 0 || (i >= 0 && horizontalCut[i] > verticalCut[j])) { ans += 1L * horizontalCut[i--] * v; ++h; } else { ans += 1L * verticalCut[j--] * h; ++v; } } return ans; }}class Solution {public: long long minimumCost(int m, int n, vector<int> &horizontalCut, vector<int> &verticalCut) { sort(horizontalCut.rbegin(), horizontalCut.rend()); sort(verticalCut.rbegin(), verticalCut.rend()); long long ans = 0; int i = 0, j = 0; int h = 1, v = 1; while (i < m - 1 || j < n - 1) { if (j == n - 1 || (i < m - 1 && horizontalCut[i] > verticalCut[j])) { ans += 1LL * horizontalCut[i++] * v; h++; } else { ans += 1LL * verticalCut[j++] * h; v++; } } return ans; }};class Solution: def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int: horizontalCut . sort(reverse=True) verticalCut . sort(reverse=True) ans = i = j = 0 h = v = 1 while i < m - 1 or j < n - 1: if j == n - 1 or (i < m - 1 and horizontalCut[i] > verticalCut[j]): ans += horizontalCut[i] * v h, i = h + 1, i + 1 else: ans += verticalCut[j] * h v, j = v + 1, j + 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.