#3219

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Cost for Cutting Cake II

Solve Minimum Cost for Cutting Cake II by choosing optimal cuts using a greedy strategy while tracking cost increments precisely.

array greedy sorting

Problem Statement

You are given an m x n cake that must be divided into 1 x 1 squares. Each cut, either horizontal or vertical, has an associated cost and can be applied to any piece larger than 1 x 1. The goal is to minimize the total cost of all cuts required to fully partition the cake.

You are provided integers m, n, and two arrays horizontalCut and verticalCut representing the costs of horizontal and vertical cuts. Each operation selects a piece not yet 1 x 1 and performs a single cut, adding its cost multiplied by the current number of segments in the perpendicular direction. Compute the minimal total cost to achieve complete 1 x 1 pieces.

Examples

Example 1

Input: m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

Output: 13

The total cost is 5 + 1 + 1 + 3 + 3 = 13 .

Example 2

Input: m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

Output: 15

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

Solution Approach

Sort Cuts Descending

Sort horizontalCut and verticalCut arrays in descending order to ensure the greedy approach picks the largest cost first, maximizing efficiency in early stages.

Greedy Cutting Loop

Iteratively choose the next largest cut from horizontal or vertical arrays, multiply its cost by the current number of segments in the perpendicular direction, add to total cost, then increment the segment count in that direction.

Invariant Cost Tracking

Maintain accurate counts of horizontal and vertical segments after each cut to guarantee each future cut cost is calculated correctly, preventing undercounting or overcounting which is the primary failure mode of this problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O((m+n) log(m+n)) due to sorting both cut arrays. Space complexity is O(1) extra beyond the input arrays, as only segment counters and total cost need storage.

What Interviewers Usually Probe

Asks how to prioritize horizontal vs vertical cuts based on cost impact.
Checks if you correctly multiply each cut cost by the current perpendicular segment count.
Probes understanding of cumulative cost tracking and failure modes when order is incorrect.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the cuts and choosing suboptimal smaller costs first.
Incorrectly calculating cost by not accounting for current perpendicular segments.
Updating segment counts in wrong order leading to overcounted or undercounted total cost.

Follow-up variants

Cutting rectangles with arbitrary costs and different unit sizes.
Maximizing revenue instead of minimizing cost with the same greedy approach.
Adding a restriction on the number of allowable cuts in one direction.

FAQ

What is the core pattern in Minimum Cost for Cutting Cake II?

The problem relies on a greedy choice plus invariant validation pattern, choosing largest cuts first and tracking perpendicular segments.

Why must cuts be sorted before processing?

Sorting ensures the greedy approach picks the largest cost first, reducing total accumulated cost efficiently.

How do you calculate the cost of each cut?

Multiply the cut value by the current number of segments in the perpendicular direction to account for its impact on all affected pieces.

What common mistakes cause wrong answers?

Mistakes include miscounting segment multipliers, choosing cuts in wrong order, or forgetting to update segment counts after each cut.

Can this approach handle large m and n efficiently?

Yes, sorting followed by greedy selection runs in O((m+n) log(m+n)) time, which scales well for m, n up to 10^5.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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 ans

Continue Practicing

#3218 minimum cost for cutting cake i #3273 minimum amount of damage dealt to bob #3281 maximize score of numbers in ranges