#1465

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

expert · 1000 · lc medium +32 · verified · 41.4% accepted · 2,642 likes · top 22%

Description

A rectangular cake measures h x w. You are given arrays horizontalCuts and verticalCuts specifying cut distances from the top and left edges respectively. After making all specified cuts, find the area of the largest resulting piece. Return this area modulo 10⁹ + 7.

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]

Output: 4

Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]

Output: 6

Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]

Output: 9

Code

1

2

3

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int: