Skip to content

1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts 👍

  • Time: $O(\texttt{sort}(\texttt{horizontalCuts}) + \texttt{sort}(\texttt{verticalCuts}))$
  • Space: $O(\texttt{sort}(\texttt{horizontalCuts}) + \texttt{sort}(\texttt{verticalCuts}))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int maxArea(int h, int w, vector<int>& horizontalCuts,
              vector<int>& verticalCuts) {
    constexpr int kMod = 1'000'000'007;
    ranges::sort(horizontalCuts);
    ranges::sort(verticalCuts);

    // the maximum gap of each direction
    int maxGapX = max(verticalCuts[0], w - verticalCuts.back());
    int maxGapY = max(horizontalCuts[0], h - horizontalCuts.back());

    for (int i = 1; i < verticalCuts.size(); ++i)
      maxGapX = max(maxGapX, verticalCuts[i] - verticalCuts[i - 1]);

    for (int i = 1; i < horizontalCuts.size(); ++i)
      maxGapY = max(maxGapY, horizontalCuts[i] - horizontalCuts[i - 1]);

    return static_cast<long>(maxGapX) * maxGapY % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
    final int kMod = 1_000_000_007;
    Arrays.sort(horizontalCuts);
    Arrays.sort(verticalCuts);

    // the maximum gap of each direction
    int maxGapX = Math.max(verticalCuts[0], w - verticalCuts[verticalCuts.length - 1]);
    int maxGapY = Math.max(horizontalCuts[0], h - horizontalCuts[horizontalCuts.length - 1]);

    for (int i = 1; i < verticalCuts.length; ++i)
      maxGapX = Math.max(maxGapX, verticalCuts[i] - verticalCuts[i - 1]);

    for (int i = 1; i < horizontalCuts.length; ++i)
      maxGapY = Math.max(maxGapY, horizontalCuts[i] - horizontalCuts[i - 1]);

    return (int) ((long) maxGapX * maxGapY % kMod);
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
    kMod = 1_000_000_007
    # the maximum gap of each direction
    maxGapX = max(b - a
                  for a, b in itertools.pairwise([0] + sorted(horizontalCuts) + [h]))
    maxGapY = max(b - a
                  for a, b in itertools.pairwise([0] + sorted(verticalCuts) + [w]))
    return maxGapX * maxGapY % kMod