Skip to main content
Back to problems
#3219
Hard Algorithms

Minimum cost for cutting cake ii

Array Greedy Sorting
55.2% acceptance
Feb 25, 2026
126
18
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 and verticalCut of size n - 1. horizontalCut[i] represents the cost to cut along the horizontal line i. verticalCut[j] represents the cost to cut along the vertical line j. Return the minimum total cost to cut the entire cake into 1 x 1 pieces.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn minimum_cost(m: i32, n: i32, horizontal_cut: Vec<i32>, vertical_cut: Vec<i32>) -> i64 {
    let _ = (m, n);
    let mut h = horizontal_cut;
    let mut v = vertical_cut;
    h.sort_unstable_by(|a, b| b.cmp(a));
    v.sort_unstable_by(|a, b| b.cmp(a));
    let mut total = 0i64;
    let mut h_pieces = 1i64;
    let mut v_pieces = 1i64;
    let mut hi = 0;
    let mut vi = 0;
    while hi < h.len() || vi < v.len() {
      let hc = h.get(hi).copied().unwrap_or(0) as i64;
      let vc = v.get(vi).copied().unwrap_or(0) as i64;
      if hc >= vc {
        total += hc * v_pieces;
        h_pieces += 1;
        hi += 1;
      } else {
        total += vc * h_pieces;
        v_pieces += 1;
        vi += 1;
      }
    }
    total
  }
}