Problem statement

https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/

Solution

Let us add border cuts to our horizontal and vertical cuts. Then all we need to do is consider all horizontal gaps between adjacent cuts, all vertical gaps between adjacent cuts, choose the biggest among each group and multiply them. Why it will work? Imagine, that we have horizontal gaps say 1, 7, 3 and vertical gaps 8, 3, 9, then maximum among products of numbers max(1*8, 1*3, 1*9, 7*8, 7*3, 7*9, 3*8, 3*3, 3*9) = 7*9.

Complexity

Time complexity is O(h*log h + v*log v) to sort our gaps, space complexity is O(v + h).

Code

class Solution:
    def maxArea(self, h, w, horizontalCuts, verticalCuts):
        H = sorted([0] + horizontalCuts + [h])
        V = sorted([0] + verticalCuts + [w])
        return max(j-i for i,j in zip(H, H[1:])) * max(j-i for i,j in zip(V, V[1:])) % (10**9 + 7)