Tejav
#1465

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

Medium
ArrayGreedySortingSortingGreedy
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n log n)
Space
O(1)
O(1)
💡

Intuition

Time O(n log n)Space O(1)

The optimal solution leverages sorting and finding the maximum gaps between cuts, which allows us to compute the maximum area efficiently without checking every combination.

⚙️

Algorithm

4 steps
  1. 1Step 1: Sort the horizontalCuts and verticalCuts arrays.
  2. 2Step 2: Calculate the maximum height by finding the maximum difference between consecutive horizontal cuts and the edges of the cake.
  3. 3Step 3: Calculate the maximum width similarly for vertical cuts.
  4. 4Step 4: The maximum area is the product of the maximum height and width, modulo 10^9 + 7.
solution.py12 lines
1# Full working Python code
2
3def maxArea(h, w, horizontalCuts, verticalCuts):
4    horizontalCuts.sort()
5    verticalCuts.sort()
6    max_height = max(horizontalCuts[0], h - horizontalCuts[-1])
7    max_width = max(verticalCuts[0], w - verticalCuts[-1])
8    for i in range(1, len(horizontalCuts)):
9        max_height = max(max_height, horizontalCuts[i] - horizontalCuts[i - 1])
10    for i in range(1, len(verticalCuts)):
11        max_width = max(max_width, verticalCuts[i] - verticalCuts[i - 1])
12    return (max_height * max_width) % (10**9 + 7)
ℹ

Complexity note: The time complexity is dominated by the sorting step, which is O(n log n), while the space complexity is O(1) since we are using a constant amount of extra space.

  • 1Sorting the cuts helps in easily finding the maximum gaps.
  • 2The maximum area is determined by the largest piece formed by the cuts.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.