LeetCode 3219 - Minimum Cost for Cutting Cake II

We are given an m x n rectangular cake and need to divide it completely into 1 x 1 pieces. The cake can be cut along predefined horizontal and vertical lines.

leetcodehardarraygreedysorting

LeetCode Problem 3219

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

We are given an m x n rectangular cake and need to divide it completely into 1 x 1 pieces. The cake can be cut along predefined horizontal and vertical lines.

There are m - 1 possible horizontal cuts and n - 1 possible vertical cuts:

  • horizontalCut[i] is the cost of cutting across horizontal line i
  • verticalCut[j] is the cost of cutting across vertical line j

A cut can only be applied to a single existing piece at a time. Once the cake has already been split into multiple pieces, applying a cut line again may need to be repeated on several subpieces.

The key detail is that the cost of a cut line is fixed, but the number of times we must apply that cut depends on how many segments currently exist in the opposite direction.

Suppose we perform a horizontal cut when there are already v vertical sections. Then that horizontal cut must be applied separately across all v pieces, so its total contribution becomes:

$$\text{horizontal cost} \times v$$

Similarly, if we perform a vertical cut when there are h horizontal sections, the total contribution becomes:

$$\text{vertical cost} \times h$$

The goal is to choose the order of cuts that minimizes the total cost.

The constraints are large:

  • m, n <= 10^5
  • Costs arrays can each contain up to 10^5 elements

This immediately tells us that any exponential or quadratic simulation will be too slow. We need an algorithm close to:

$$O((m+n)\log(m+n))$$

Important edge cases include:

  • Only one row or one column, meaning one of the cut arrays is empty
  • All cuts having identical costs
  • Extremely unbalanced costs where one direction contains very large values
  • Large inputs where inefficient repeated scanning would time out

The problem guarantees all costs are positive integers, which is important because it enables a greedy strategy based on taking larger costs earlier.

Approaches

Brute Force Approach

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

At every step, we can choose one remaining horizontal cut or one remaining vertical cut. Since there are (m - 1) + (n - 1) total cuts, the number of possible orders is factorial in the number of cuts.

For each ordering, we could simulate the process:

  • Track how many horizontal and vertical segments currently exist
  • Compute the contribution of each cut
  • Keep the minimum total

This produces the correct answer because it explicitly evaluates all valid sequences of operations.

However, this approach is completely infeasible. Even with only 20 cuts, the number of permutations becomes astronomically large.

Key Insight

The important observation is that expensive cuts should be performed as early as possible.

Why?

Because every future cut in the opposite direction increases the multiplier for this cut.

Suppose we delay a very expensive horizontal cut until after many vertical cuts have already been made. Then that expensive cut must be repeated across many vertical segments, dramatically increasing its total contribution.

Instead, we should apply large costs while the multiplier is still small.

This leads directly to a greedy strategy:

  • Always perform the currently most expensive remaining cut
  • Process cuts in descending order

This is exactly the same principle used in the classic "board cutting" greedy problem.

After sorting both arrays in descending order, we repeatedly choose:

  • The next largest horizontal cut
  • Or the next largest vertical cut

whichever is larger.

Because all costs are positive, taking the larger cut earlier can never hurt and always minimizes its multiplication factor.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force $O((m+n)!)$ $O(m+n)$ Tries every possible ordering of cuts
Optimal Greedy $O((m+n)\log(m+n))$ $O(1)$ extra, excluding sorting Sort descending and always take largest remaining cut

Algorithm Walkthrough

  1. Sort both horizontalCut and verticalCut in descending order.

We want to process expensive cuts first so that they are multiplied by as few segments as possible. 2. Maintain two counters:

  • horizontal_segments
  • vertical_segments

Initially:

  • horizontal_segments = 1
  • vertical_segments = 1

because the cake starts as one single piece. 3. Use two pointers:

  • i for horizontal cuts
  • j for vertical cuts
  1. While both arrays still contain unused cuts:

  • Compare horizontalCut[i] and verticalCut[j]

  • If the horizontal cost is larger:

  • Add:

$$horizontalCut[i] \times vertical_segments$$

  • Increment horizontal_segments

  • Move i

  • Otherwise:

  • Add:

$$verticalCut[j] \times horizontal_segments$$

  • Increment vertical_segments
  • Move j
  1. After one array is exhausted, process all remaining cuts from the other array.
  2. Return the accumulated total cost.

Why it works

The greedy choice is optimal because every cut cost is multiplied by the number of segments in the opposite direction.

Suppose we have two remaining cuts:

  • A larger cost A
  • A smaller cost B

If we apply A later, it will be multiplied by a larger segment count than if we apply it now. Since A > B, delaying A increases the total cost more than delaying B.

Therefore, larger cuts should always be processed earlier.

This exchange argument proves the correctness of the greedy ordering.

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)

        h_segments = 1
        v_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] * v_segments
                h_segments += 1
                i += 1
            else:
                total_cost += verticalCut[j] * h_segments
                v_segments += 1
                j += 1

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

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

        return total_cost

The implementation begins by sorting both cut arrays in descending order. This guarantees that we always consider the most expensive remaining cut first.

The variables h_segments and v_segments track how many pieces currently exist in each direction. Every time we make a horizontal cut, the number of horizontal segments increases by one. Similarly, every vertical cut increases the number of vertical segments.

The two-pointer merge process resembles merging two sorted arrays. At each step, we greedily choose the larger remaining cut because applying expensive cuts earlier minimizes their multiplier.

Once one array is exhausted, the remaining cuts are processed directly since there is no longer any choice to make.

The algorithm uses only linear scanning after sorting, making it efficient enough for the large constraints.

Go Solution

package main

import "sort"

func minimumCost(m int, n int, horizontalCut []int, verticalCut []int) int64 {

	sort.Slice(horizontalCut, func(i, j int) bool {
		return horizontalCut[i] > horizontalCut[j]
	})

	sort.Slice(verticalCut, func(i, j int) bool {
		return verticalCut[i] > verticalCut[j]
	})

	hSegments := int64(1)
	vSegments := int64(1)

	i := 0
	j := 0

	var totalCost int64 = 0

	for i < len(horizontalCut) && j < len(verticalCut) {

		if horizontalCut[i] > verticalCut[j] {
			totalCost += int64(horizontalCut[i]) * vSegments
			hSegments++
			i++
		} else {
			totalCost += int64(verticalCut[j]) * hSegments
			vSegments++
			j++
		}
	}

	for i < len(horizontalCut) {
		totalCost += int64(horizontalCut[i]) * vSegments
		hSegments++
		i++
	}

	for j < len(verticalCut) {
		totalCost += int64(verticalCut[j]) * hSegments
		vSegments++
		j++
	}

	return totalCost
}

The Go implementation follows exactly the same greedy strategy as the Python version.

One important difference is integer handling. Since the total cost can become large, the function returns int64. Every multiplication is explicitly converted to int64 before accumulation to avoid overflow on systems where int is 32-bit.

The sorting uses sort.Slice with a custom comparator to produce descending order.

Worked Examples

Example 1

Input:

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

After sorting:

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

Initial state:

h_segments = 1
v_segments = 1
total = 0
Step Chosen Cut Cost Formula Added Cost h_segments v_segments Total
1 Vertical 5 $5 \times 1$ 5 1 2 5
2 Horizontal 3 $3 \times 2$ 6 2 2 11
3 Horizontal 1 $1 \times 2$ 2 3 2 13

Final answer:

13

Example 2

Input:

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

After sorting:

horizontalCut = [7]
verticalCut = [4]

Initial state:

h_segments = 1
v_segments = 1
total = 0
Step Chosen Cut Cost Formula Added Cost h_segments v_segments Total
1 Horizontal 7 $7 \times 1$ 7 2 1 7
2 Vertical 4 $4 \times 2$ 8 2 2 15

Final answer:

15

Complexity Analysis

Measure Complexity Explanation
Time $O((m+n)\log(m+n))$ Sorting dominates the runtime
Space $O(1)$ extra Only pointers and counters are used beyond sorting

The main cost comes from sorting the two arrays. After sorting, the merge-like greedy scan is linear.

If the language's sorting implementation requires auxiliary memory internally, that memory usage is implementation-dependent, but the algorithm itself uses constant additional space.

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)

        h_segments = 1
        v_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] * v_segments
                h_segments += 1
                i += 1
            else:
                total_cost += verticalCut[j] * h_segments
                v_segments += 1
                j += 1

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

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

        return total_cost

sol = Solution()

assert sol.minimumCost(3, 2, [1, 3], [5]) == 13
# basic mixed example

assert sol.minimumCost(2, 2, [7], [4]) == 15
# smallest non-trivial grid

assert sol.minimumCost(1, 4, [], [1, 2, 3]) == 6
# only vertical cuts

assert sol.minimumCost(5, 1, [1, 2, 3, 4], []) == 10
# only horizontal cuts

assert sol.minimumCost(3, 3, [1, 1], [1, 1]) == 8
# all costs equal

assert sol.minimumCost(3, 3, [1000, 1], [1, 1]) == 1006
# one extremely expensive cut

assert sol.minimumCost(4, 4, [2, 1, 3], [4, 1, 2]) == 24
# general mixed ordering case

assert sol.minimumCost(2, 5, [10], [1, 1, 1, 1]) == 18
# expensive horizontal cut should happen first

assert sol.minimumCost(5, 2, [1, 1, 1, 1], [10]) == 18
# expensive vertical cut should happen first
Test Why
m=3, n=2 example Validates standard mixed-case behavior
m=2, n=2 example Validates smallest meaningful grid
Only vertical cuts Ensures empty horizontal array works
Only horizontal cuts Ensures empty vertical array works
All equal costs Confirms tie handling correctness
One huge cost Validates greedy ordering importance
Mixed ordering Tests repeated switching between directions
Expensive horizontal cut Ensures large cuts occur early
Expensive vertical cut Symmetric validation of greedy logic

Edge Cases

One important edge case occurs when one dimension is already size 1. For example, if m = 1, then there are no horizontal cuts at all. A buggy implementation might assume both arrays are non-empty or fail during pointer traversal. This implementation handles the situation naturally because the main loop terminates immediately and the remaining vertical cuts are processed correctly.

Another important case is when all cut costs are identical. In this situation, many different orders produce the same optimal answer. Some implementations accidentally rely on strict inequalities and may mishandle ties. Here, ties are safely resolved by taking the vertical cut in the else branch, but any tie order works because the costs are equal.

A third critical edge case involves extremely unbalanced costs, such as one very large cut and many tiny cuts. A naive strategy that processes cuts in arbitrary order can become dramatically suboptimal. The greedy descending-order approach specifically prevents expensive cuts from being multiplied by large segment counts, which is exactly why it produces the minimum total cost.

Another subtle case is large input size. Since both arrays can contain up to 10^5 elements, any repeated rescanning or nested looping would time out. The implementation avoids this by sorting once and then scanning both arrays exactly once with two pointers.