Watch 10 video solutions for Minimum Cost for Cutting Cake II, a hard level problem involving Array, Greedy, Sorting. This walkthrough by codestorywithMIK has 5,654 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |