LeetCode 3218 - Minimum Cost for Cutting Cake I

The problem gives us an m x n rectangular cake and asks us to cut it into individual 1 x 1 pieces. We are allowed to cut along predefined horizontal and vertical lines. Each line has a fixed cost associated with it.

leetcodemediumarraytwo-pointersdynamic-programminggreedysorting

LeetCode Problem 3218

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Dynamic Programming, Greedy, Sorting

Solution

Problem Understanding

The problem gives us an m x n rectangular cake and asks us to cut it into individual 1 x 1 pieces. We are allowed to cut along predefined horizontal and vertical lines. Each line has a fixed cost associated with it.

The important detail is that the same cut may need to be applied multiple times across different subpieces of the cake. When we cut a cake piece along a horizontal line, that cut affects only the specific piece we selected, not the entire cake globally. The same is true for vertical cuts.

Suppose we perform a vertical cut first. That divides the cake into multiple vertical sections. Later, every horizontal cut may need to be repeated across each vertical section separately. Because of this interaction, the order of cuts changes the total cost significantly.

The input consists of:

  • m, the number of rows in the cake
  • n, the number of columns in the cake
  • horizontalCut, an array of size m - 1
  • verticalCut, an array of size n - 1

Each value in horizontalCut represents the cost of cutting along one horizontal boundary. Each value in verticalCut represents the cost of cutting along one vertical boundary.

The goal is to minimize the total cutting cost required to divide the cake completely into 1 x 1 pieces.

The constraints are relatively small:

  • 1 <= m, n <= 20
  • Costs are at most 1000

Even though the dimensions are small, the number of possible cut orders grows extremely quickly. This suggests that a brute-force simulation of all cutting sequences is not practical.

Several edge cases are important to notice immediately.

If m = 1, then there are no horizontal cuts. We only need vertical cuts. Similarly, if n = 1, only horizontal cuts are needed.

Another important case is when one cut cost is much larger than the others. In that situation, the order of operations becomes critical because expensive cuts should ideally happen before the cake is divided into many pieces.

We also need to correctly handle repeated multiplication effects. A horizontal cut performed after many vertical splits becomes much more expensive because it must be applied to every vertical segment.

Approaches

Brute Force Approach

A brute-force solution would try every possible order of cuts.

At each step, we could choose one remaining horizontal or vertical cut and recursively continue until all cuts are used. For every sequence, we compute the total cost and keep the minimum.

This approach is correct because it explores every possible valid cutting order. Eventually, it will discover the optimal sequence.

However, it becomes computationally infeasible very quickly. If there are m - 1 horizontal cuts and n - 1 vertical cuts, then the total number of cut orderings is:

$$(m + n - 2)!$$

Even for moderate values, this becomes enormous.

Optimal Greedy Insight

The key observation is that expensive cuts should happen earlier.

Suppose we have a large horizontal cut cost. If we delay it until after many vertical splits exist, then that expensive cut must be applied across many vertical pieces, multiplying its contribution.

To minimize total cost, we want large costs to be multiplied by smaller segment counts.

This naturally leads to a greedy strategy:

  • Always perform the currently most expensive cut first
  • Keep track of how many horizontal and vertical segments currently exist
  • A horizontal cut cost is multiplied by the current number of vertical segments
  • A vertical cut cost is multiplied by the current number of horizontal segments

This works because the multiplication factor only increases over time. Therefore, delaying expensive cuts is always disadvantageous.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((m+n)!) O(m+n) Tries every possible cut ordering
Optimal Greedy O(m log m + n log n) O(1) excluding sorting Sort cuts descending and greedily apply largest first

Algorithm Walkthrough

  1. Sort both horizontalCut and verticalCut in descending order.

We want to process expensive cuts first because future multipliers only increase. Sorting descending ensures we always consider the largest remaining cut. 2. Initialize segment counters.

Initially, the cake is one whole piece:

  • horizontal_segments = 1
  • vertical_segments = 1

These counters represent how many pieces exist in each direction. 3. Use two pointers.

Maintain:

  • i for horizontal cuts
  • j for vertical cuts

Since both arrays are sorted descending, these pointers track the next largest available cut. 4. Compare the next horizontal and vertical cut.

If the next horizontal cut is larger:

  • Add horizontalCut[i] * vertical_segments
  • Increment horizontal_segments
  • Move i

Otherwise:

  • Add verticalCut[j] * horizontal_segments
  • Increment vertical_segments
  • Move j

The multiplication happens because the cut must be applied across every segment in the opposite direction. 5. Process remaining cuts.

Once one array is exhausted, process all remaining cuts from the other array using the current segment multiplier. 6. Return the accumulated total cost.

Why it works

The greedy strategy works because every future cut multiplier is monotonically increasing. If we delay a large cut, it will eventually be multiplied by a larger number of segments. Swapping a large delayed cut with a smaller earlier cut can never improve the result. Therefore, performing larger cuts earlier always leads to an optimal solution.

Python Solution

from typing import List

class Solution:
    def minimumCost(
        self,
        m: int,
        n: int,
        horizontalCut: List[int],
        verticalCut: List[int]
    ) -> int:
        
        horizontalCut.sort(reverse=True)
        verticalCut.sort(reverse=True)

        horizontal_segments = 1
        vertical_segments = 1

        i = 0
        j = 0

        total_cost = 0

        while i < len(horizontalCut) and j < len(verticalCut):
            if horizontalCut[i] > verticalCut[j]:
                total_cost += horizontalCut[i] * vertical_segments
                horizontal_segments += 1
                i += 1
            else:
                total_cost += verticalCut[j] * horizontal_segments
                vertical_segments += 1
                j += 1

        while i < len(horizontalCut):
            total_cost += horizontalCut[i] * vertical_segments
            horizontal_segments += 1
            i += 1

        while j < len(verticalCut):
            total_cost += verticalCut[j] * horizontal_segments
            vertical_segments += 1
            j += 1

        return total_cost

The implementation begins by sorting both cut arrays in descending order. This guarantees that the most expensive cuts are considered first.

The variables horizontal_segments and vertical_segments track how many pieces currently exist in each direction. Initially, the entire cake is one piece, so both values start at 1.

The two-pointer traversal compares the next largest horizontal and vertical cut. When applying a horizontal cut, the cost is multiplied by the number of vertical segments because that cut must be repeated across every vertical piece. The opposite logic applies for vertical cuts.

After one array is exhausted, the remaining cuts are processed sequentially with the current segment multiplier.

The final answer is the accumulated total cost.

Go Solution

package main

import (
	"sort"
)

func minimumCost(m int, n int, horizontalCut []int, verticalCut []int) int {
	sort.Sort(sort.Reverse(sort.IntSlice(horizontalCut)))
	sort.Sort(sort.Reverse(sort.IntSlice(verticalCut)))

	horizontalSegments := 1
	verticalSegments := 1

	i := 0
	j := 0

	totalCost := 0

	for i < len(horizontalCut) && j < len(verticalCut) {
		if horizontalCut[i] > verticalCut[j] {
			totalCost += horizontalCut[i] * verticalSegments
			horizontalSegments++
			i++
		} else {
			totalCost += verticalCut[j] * horizontalSegments
			verticalSegments++
			j++
		}
	}

	for i < len(horizontalCut) {
		totalCost += horizontalCut[i] * verticalSegments
		horizontalSegments++
		i++
	}

	for j < len(verticalCut) {
		totalCost += verticalCut[j] * horizontalSegments
		verticalSegments++
		j++
	}

	return totalCost
}

The Go implementation follows exactly the same logic as the Python version.

Go requires explicit sorting utilities, so we use sort.Sort(sort.Reverse(sort.IntSlice(...))) to sort descending.

Slices are used directly for the cut arrays. Since the maximum possible cost easily fits within Go's int range under the given constraints, no special overflow handling is necessary.

Worked Examples

Example 1

Input:

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

After sorting:

horizontalCut = [3, 1]
verticalCut = [5]

Initial state:

Variable Value
horizontal_segments 1
vertical_segments 1
total_cost 0

Step 1:

Compare 3 and 5.

Since 5 is larger, perform vertical cut.

Cost added:

5 × 1 = 5

Updated state:

Variable Value
horizontal_segments 1
vertical_segments 2
total_cost 5

Step 2:

Only horizontal cuts remain.

Perform cut 3.

Cost added:

3 × 2 = 6

Updated state:

Variable Value
horizontal_segments 2
vertical_segments 2
total_cost 11

Step 3:

Perform cut 1.

Cost added:

1 × 2 = 2

Final total:

11 + 2 = 13

Answer:

13

Example 2

Input:

m = 2
n = 2
horizontalCut = [7]
verticalCut = [4]

After sorting:

horizontalCut = [7]
verticalCut = [4]

Initial state:

Variable Value
horizontal_segments 1
vertical_segments 1
total_cost 0

Step 1:

Compare 7 and 4.

Since 7 is larger, perform horizontal cut.

Cost added:

7 × 1 = 7

Updated state:

Variable Value
horizontal_segments 2
vertical_segments 1
total_cost 7

Step 2:

Perform remaining vertical cut.

Cost added:

4 × 2 = 8

Final total:

7 + 8 = 15

Answer:

15

Complexity Analysis

Measure Complexity Explanation
Time O(m log m + n log n) Dominated by sorting both cut arrays
Space O(1) excluding sorting Only a few variables are used

The algorithm spends most of its time sorting the horizontal and vertical cut arrays. After sorting, the merge-like traversal is linear in the number of cuts. No additional data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def minimumCost(
        self,
        m: int,
        n: int,
        horizontalCut: List[int],
        verticalCut: List[int]
    ) -> int:
        
        horizontalCut.sort(reverse=True)
        verticalCut.sort(reverse=True)

        horizontal_segments = 1
        vertical_segments = 1

        i = 0
        j = 0

        total_cost = 0

        while i < len(horizontalCut) and j < len(verticalCut):
            if horizontalCut[i] > verticalCut[j]:
                total_cost += horizontalCut[i] * vertical_segments
                horizontal_segments += 1
                i += 1
            else:
                total_cost += verticalCut[j] * horizontal_segments
                vertical_segments += 1
                j += 1

        while i < len(horizontalCut):
            total_cost += horizontalCut[i] * vertical_segments
            i += 1

        while j < len(verticalCut):
            total_cost += verticalCut[j] * horizontal_segments
            j += 1

        return total_cost

sol = Solution()

assert sol.minimumCost(3, 2, [1, 3], [5]) == 13  # provided example 1
assert sol.minimumCost(2, 2, [7], [4]) == 15  # provided example 2
assert sol.minimumCost(1, 4, [], [1, 2, 3]) == 6  # only vertical cuts
assert sol.minimumCost(4, 1, [2, 2, 2], []) == 6  # only horizontal cuts
assert sol.minimumCost(2, 3, [1], [1, 1]) == 5  # equal costs
assert sol.minimumCost(3, 3, [10, 1], [1, 1]) == 15  # expensive cut first
assert sol.minimumCost(3, 3, [5, 5], [5, 5]) == 40  # all equal costs
assert sol.minimumCost(2, 2, [1000], [1000]) == 3000  # maximum cut values

Test Summary

Test Why
m=3, n=2 Validates provided example
m=2, n=2 Verifies second provided example
m=1 Tests absence of horizontal cuts
n=1 Tests absence of vertical cuts
Equal cut costs Ensures tie handling works correctly
One very large cut Verifies greedy ordering importance
All equal large grid Confirms repeated multipliers are handled
Maximum cut values Tests upper bound cost handling

Edge Cases

One important edge case occurs when m = 1 or n = 1. In these situations, one of the cut arrays is empty. A buggy implementation might assume both arrays contain elements and accidentally access invalid indices. This implementation handles the situation naturally because the main loop stops immediately, and only the remaining cuts loop executes.

Another important case is when many cut costs are identical. Some implementations incorrectly rely on strict ordering assumptions. Here, ties are handled safely because choosing either equal-cost cut first produces the same total contribution structure. The algorithm still remains optimal.

A third critical edge case occurs when one cut cost is significantly larger than all others. For example, a single cut with cost 1000 and many cuts with cost 1. If the expensive cut is delayed, it gets multiplied by many segments and dramatically increases the total cost. The greedy descending-order strategy ensures large cuts happen as early as possible, minimizing their multiplier.

A final subtle case involves fully exhausting one cut array before the other. Some implementations forget to process the remaining cuts afterward. This solution explicitly includes separate loops for remaining horizontal and vertical cuts, guaranteeing all required cuts are applied exactly once.