Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts - Video Solutions

Problem Overview: A rectangular cake of size h × w is cut using horizontal and vertical cut positions. Each cut divides the cake completely across that axis. After all cuts are applied, multiple smaller rectangles are formed. The task is to compute the maximum possible area of any resulting piece. Because the result can be large, return it modulo 1e9 + 7.

Approach 1: Sort and Find Maximum Gaps (Greedy) (Time: O(n log n), Space: O(1) or O(n) depending on sorting)

The key observation: the largest piece must come from the largest distance between two consecutive horizontal cuts and the largest distance between two consecutive vertical cuts. First sort both cut arrays using a standard sorting routine. Then iterate through each list to compute the maximum gap between adjacent cuts. Remember to also check the edges: 0 → first_cut and last_cut → h (or w). The maximum horizontal gap multiplied by the maximum vertical gap gives the largest rectangle area. This approach works because cuts partition the cake into independent intervals; maximizing each dimension independently yields the optimal rectangle. The final multiplication is taken modulo 1e9+7. This method relies on simple iteration over an array and a greedy selection of the largest gaps.

Approach 2: Dynamic Programming with Memoization (Time: O(n × m), Space: O(n × m))

A more exploratory method models the cake as segments between cuts and recursively computes the maximum area achievable from combinations of horizontal and vertical partitions. Memoization stores results for subproblems defined by index ranges between cuts. For each state, the algorithm considers potential partitions and calculates the maximum area from resulting segments. Although this demonstrates how subproblems overlap and how memoization avoids recomputation, it is less efficient than the greedy observation because the rectangle area is determined solely by the largest gaps. The DP approach is mostly educational for practicing recursion and caching patterns often seen in greedy-vs-DP comparisons.

Recommended for interviews: Interviewers expect the sorting + maximum gap insight. A brute or DP-style exploration shows you understand the partitioning idea, but recognizing that the largest piece is defined by the largest consecutive gaps demonstrates algorithmic clarity. The optimal solution runs in O(n log n) due to sorting and O(1) additional space, which is efficient even for large cut arrays.