Minimum cost for cutting cake i

Array Two Pointers Dynamic Programming Greedy Sorting

58.4% acceptance

Feb 25, 2026

203

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: Cut along a horizontal line i at a cost of horizontalCut[i]. Cut along a vertical line 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.

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>) -> i32 {
    let _ = (m, n);
    let mut h = horizontal_cut;
    let mut v = vertical_cut;
    h.sort_unstable_by(|a, b| b.cmp(a)); // descending
    v.sort_unstable_by(|a, b| b.cmp(a)); // descending
    let mut total = 0i32;
    let mut h_pieces = 1i32;
    let mut v_pieces = 1i32;
    let mut hi = 0;
    let mut vi = 0;
    while hi < h.len() || vi < v.len() {
      let hc = h.get(hi).copied().unwrap_or(0);
      let vc = v.get(vi).copied().unwrap_or(0);
      if hc >= vc {
        total += hc * v_pieces;
        h_pieces += 1;
        hi += 1;
      } else {
        total += vc * h_pieces;
        v_pieces += 1;
        vi += 1;
      }
    }
    total
  }
}