Maximum area of a piece of cake after horizontal and vertical cuts

Array Greedy Sorting

41.4% acceptance

Feb 25, 2026

2642

353

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where: horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut. Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 10^9 + 7.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_area(h: i32, w: i32, mut horizontal_cuts: Vec<i32>, mut vertical_cuts: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    horizontal_cuts.sort_unstable();
    vertical_cuts.sort_unstable();
    let max_h = {
      let mut prev = 0i64;
      let mut max_gap = 0i64;
      for &c in &horizontal_cuts {
        max_gap = max_gap.max(c as i64 - prev);
        prev = c as i64;
      }
      max_gap.max(h as i64 - prev)
    };
    let max_v = {
      let mut prev = 0i64;
      let mut max_gap = 0i64;
      for &c in &vertical_cuts {
        max_gap = max_gap.max(c as i64 - prev);
        prev = c as i64;
      }
      max_gap.max(w as i64 - prev)
    };
    ((max_h % MOD) * (max_v % MOD) % MOD) as i32
  }
}