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

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

What is this problem about?

You are given a rectangular cake with height h and width w. You are also given two arrays: horizontalCuts and verticalCuts. These arrays represent the coordinates where you will slice the cake. After making all the cuts, the cake is divided into multiple smaller rectangular pieces. Your objective is to find the maximum area among all these resulting pieces, returning the answer modulo $10^9 + 7$.

Why is this asked in interviews?

This is a visual geometry problem that tests a candidate's ability to decouple axes. Interviewers ask it because candidates who try to physically model the grid and calculate the area of every single resulting piece ($O(H \times V)$) will fail the time constraints. It evaluates whether you can deduce that the largest area is simply the product of the largest horizontal gap and the largest vertical gap.

Algorithmic pattern used

This utilizes a Sorting and Greedy Gap pattern.

1. The horizontal cuts and vertical cuts are entirely independent. A piece's height is determined by the distance between two adjacent horizontal cuts. A piece's width is determined by two adjacent vertical cuts.
2. Sort the horizontalCuts array and the verticalCuts array.
3. Iterate through horizontalCuts to find the maximum difference between any two adjacent cuts. Don't forget to check the edges (distance from 0 to the first cut, and the last cut to h).
4. Do the same for verticalCuts to find the maximum width.
5. Multiply the max height by the max width, apply the modulo, and return.

Example explanation

Cake h = 5, w = 4. horizontalCuts = [1, 2, 4] verticalCuts = [1, 3]

Analyze horizontal gaps:

• 0 to 1 = gap 1
• 1 to 2 = gap 1
• 2 to 4 = gap 2
• 4 to 5 (h) = gap 1 Max horizontal gap (height) = 2.

Analyze vertical gaps:

• 0 to 1 = gap 1
• 1 to 3 = gap 2
• 3 to 4 (w) = gap 1 Max vertical gap (width) = 2.

The largest piece of cake has dimensions $2 \times 2$. Area is 4.

Common mistakes candidates make

A very common mistake is forgetting to evaluate the boundary edges of the cake. Candidates often just loop arr[i] - arr[i-1] and completely forget that a piece of cake exists between the top edge 0 and the first cut, and between the last cut and the far edge h or w. Another mistake is multiplying the two large gaps using standard 32-bit integers, which will cause an overflow before the modulo is applied. You must cast them to long before multiplying.

Interview preparation tip

For the Maximum Area of a Piece of Cake coding problem, write a clean helper function: long getMaxGap(int[] cuts, int maxEdge). Inside, sort the array, calculate maxGap = Math.max(cuts[0], maxEdge - cuts[cuts.length - 1]), then loop through the inner cuts. This shows strong software engineering principles (DRY code) and prevents copy-paste errors.