Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

MediumGreedygreedy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A rectangular cake has height h and width w. horizontalCuts[i] is the distance from the top edge to the i-th horizontal cut, and verticalCuts[j] is the distance from the left edge to the j-th vertical cut. Cut positions are distinct within each array and lie strictly inside the cake, but they are **not** sorted. After making every cut, return the largest area among the resulting pieces. Because the area can be huge, return it modulo 10^9 + 7. Take the modulo only at the end: find the true maximum area first. Target O(H log H + V log V) time.

Examples

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4
The tallest strip is 2 (between 2 and 4) and the widest is 2 (between 1 and 3), so 2 * 2 = 4.
Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Gaps of 2 (between 3 and 5) and 3 (between 1 and 4) give 6.
Input: h = 1000000000, w = 1000000000, horizontalCuts = [2], verticalCuts = [2]
Output: 81
The largest piece is 999999998 * 999999998 = 999999996000000004, which is 81 modulo 10^9 + 7.

Constraints

  • 2 <= h, w <= 10^9
  • 1 <= horizontalCuts.length <= min(h - 1, 10^5)
  • 1 <= verticalCuts.length <= min(w - 1, 10^5)
  • 1 <= horizontalCuts[i] < h and 1 <= verticalCuts[i] < w
  • All values within each cuts array are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy problems