1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Approach
Sort cuts; find max gap in horizontal and vertical cuts; answer = maxGapH × maxGapV mod 10^9+7.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
// Approach: Sort cuts; find max gap in horizontal and vertical cuts; answer = maxGapH × maxGapV mod 10^9+7.
// Time: O(n log n) Space: O(1)
public class Solution
{
public int MaxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts)
{
const int kMod = 1_000_000_007;
Array.Sort(horizontalCuts);
Array.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);
}
}