Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.
Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 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

 
Constraints:

2 <= h, w <= 10^9
1 <= horizontalCuts.length < min(h, 10^5)
1 <= verticalCuts.length < min(w, 10^5)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
It is guaranteed that all elements in horizontalCuts are distinct.
It is guaranteed that all elements in verticalCuts are distinct.

Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms
Skill types: Sorting

Data structures

Greedy algorithms

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

Solutions:
class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		mod = int(1000000000.0) + 7
		return self.getMax(horizontalCuts, h) % mod * (self.getMax(verticalCuts, w) % mod) % mod

	def getMax(self, cuts, size):
		if len(cuts) == 1:
			return max(cuts[0], size - cuts[0])
		cuts.sort()
		max_cut_size = max(cuts[0], size - cuts[-1])
		for index in range(1, len(cuts)):
			if cuts[index] - cuts[index - 1] > max_cut_size:
				max_cut_size = cuts[index] - cuts[index - 1]
		return max_cut_size


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		h_max = self.get_max_interval(w, sorted(verticalCuts))
		w_max = self.get_max_interval(h, sorted(horizontalCuts))
		return h_max * w_max % (10 ** 9 + 7)

	def get_max_interval(self, length, cuts):
		current = 0
		max_cut = 0
		for cut in cuts:
			max_cut = max(max_cut, cut - current)
			current = cut
		max_cut = max(max_cut, length - current)
		return max_cut


class Solution:

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

		def getGap(arr, n):
			prev = 0
			i = 0
			res = 0
			while i < len(arr):
				res = max(arr[i] - prev, res)
				prev = arr[i]
				i += 1
			return max(n - prev, res)
		return getGap(horizontalCuts, h) * getGap(verticalCuts, w) % (10 ** 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		n = len(horizontalCuts)
		m = len(verticalCuts)
		A = horizontalCuts[:]
		B = verticalCuts[:]
		A.sort()
		B.sort()
		A.insert(0, 0)
		B.insert(0, 0)
		A.append(h)
		B.append(w)
		maxw = 0
		maxh = 0
		for i in range(1, n + 2):
			maxh = max(maxh, A[i] - A[i - 1])
		for i in range(1, m + 2):
			maxw = max(maxw, B[i] - B[i - 1])
		m = 10 ** 9 + 7
		return maxw % m * (maxh % m) % m


class Solution:

	def maxArea(self, h: int, w: int, hc: List[int], v: List[int]) -> int:
		hc.append(0)
		hc.append(h)
		v.append(0)
		v.append(w)
		v.sort()
		hc.sort()
		max_v = max_h = 0
		for i in range(1, len(hc)):
			max_h = max(max_h, hc[i] - hc[i - 1])
		for i in range(1, len(v)):
			max_v = max(max_v, v[i] - v[i - 1])
		return max_h * max_v % 1000000007


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts = sorted(horizontalCuts)
		verticalCuts = sorted(verticalCuts)
		horizontalCuts.insert(0, 0)
		horizontalCuts.append(h)
		verticalCuts.insert(0, 0)
		verticalCuts.append(w)
		print(horizontalCuts)
		print(verticalCuts)
		maxx = 0
		for x in range(1, len(horizontalCuts)):
			maxx = max(maxx, horizontalCuts[x] - horizontalCuts[x - 1])
		maxy = 0
		for y in range(1, len(verticalCuts)):
			maxy = max(maxy, verticalCuts[y] - verticalCuts[y - 1])
		return maxx * maxy % 1000000007


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		return self.get_max_length(h, horizontalCuts) * self.get_max_length(w, verticalCuts) % 1000000007

	def get_max_length(self, length: int, cuts: List[int]) -> int:
		if len(cuts) == 1:
			return max(cuts[0], length - cuts[0])
		cuts.sort()
		max_length = max(cuts[0], length - cuts[-1])
		for i in range(1, len(cuts)):
			max_length = max(max_length, cuts[i] - cuts[i - 1])
		return max_length


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		if 0 not in horizontalCuts:
			horizontalCuts.append(0)
		if h not in horizontalCuts:
			horizontalCuts.append(h)
		if 0 not in verticalCuts:
			verticalCuts.append(0)
		if w not in verticalCuts:
			verticalCuts.append(w)
		horizontalCuts.sort()
		verticalCuts.sort()
		i = 0
		max_diff = -float('inf')
		while i in range(len(horizontalCuts) - 1):
			if horizontalCuts[i + 1] - horizontalCuts[i] > max_diff:
				max_diff = max(max_diff, horizontalCuts[i + 1] - horizontalCuts[i])
			i += 1
		j = 0
		max_diff1 = -float('inf')
		while j in range(len(verticalCuts) - 1):
			if verticalCuts[j + 1] - verticalCuts[j] > max_diff1:
				max_diff1 = max(max_diff1, verticalCuts[j + 1] - verticalCuts[j])
			j += 1
		return max_diff * max_diff1 % (10 ** 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, hh: List[int], vv: List[int]) -> int:
		hh = sorted(hh) + [h]
		vv = sorted(vv) + [w]
		prev = 0
		hm = 0
		for i in hh:
			hm = max(hm, i - prev)
			prev = i
		prev = 0
		vm = 0
		for i in vv:
			vm = max(vm, i - prev)
			prev = i
		return vm * hm % (10 ** 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, hc: List[int], vc: List[int]) -> int:
		(hc, vc) = ([0] + sorted(hc) + [h], [0] + sorted(vc) + [w])
		return max((hc[i] - hc[i - 1] for i in range(1, len(hc)))) * max((vc[i] - vc[i - 1] for i in range(1, len(vc)))) % 1000000007


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		mod = 10 ** 9 + 7
		horizontalCuts.extend([0, h])
		horizontalCuts.sort()
		verticalCuts.extend([0, w])
		verticalCuts.sort()
		hor_max = 0
		for i in range(len(horizontalCuts) - 1):
			hor_max = max(hor_max, horizontalCuts[i + 1] - horizontalCuts[i])
		ver_max = 0
		for i in range(len(verticalCuts) - 1):
			ver_max = max(ver_max, verticalCuts[i + 1] - verticalCuts[i])
		return hor_max * ver_max % mod


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		new_horizontal_cuts = [0] + sorted(horizontalCuts) + [h]
		new_vertical_cuts = [0] + sorted(verticalCuts) + [w]
		mod = int(1000000000.0) + 7
		max_height = 0
		max_width = 0
		for j in range(len(new_vertical_cuts) - 1):
			if max_width < new_vertical_cuts[j + 1] - new_vertical_cuts[j]:
				max_width = new_vertical_cuts[j + 1] - new_vertical_cuts[j]
		for i in range(len(new_horizontal_cuts) - 1):
			if max_height < new_horizontal_cuts[i + 1] - new_horizontal_cuts[i]:
				max_height = new_horizontal_cuts[i + 1] - new_horizontal_cuts[i]
		return max_width * max_height % mod


class Solution:

	def maxArea(self, h: int, w: int, hori: List[int], verti: List[int]) -> int:
		hori.sort()
		verti.sort()
		x = hori[0]
		for i in range(1, len(hori)):
			x = max(x, hori[i] - hori[i - 1])
		x = max(x, h - hori[-1])
		y = verti[0]
		for i in range(1, len(verti)):
			y = max(y, verti[i] - verti[i - 1])
		y = max(y, w - verti[-1])
		return x * y % 1000000007


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalStrips = [0] + sorted(horizontalCuts) + [h]
		verticalStrips = [0] + sorted(verticalCuts) + [w]
		maxW = max([horizontalStrips[i + 1] - horizontalStrips[i] for i in range(len(horizontalStrips) - 1)])
		maxH = max([verticalStrips[i + 1] - verticalStrips[i] for i in range(len(verticalStrips) - 1)])
		return maxW * maxH % (10 ** 9 + 7)


class Solution:

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

		def getMaxSpace(cuts, upperLimit):
			cuts = sorted(cuts)
			if not any(cuts):
				return upperLimit
			ans = cuts[0]
			for i in range(len(cuts) - 1):
				ans = max(ans, cuts[i + 1] - cuts[i])
			return max(ans, upperLimit - cuts[-1])
		maxHorSpace = getMaxSpace(horizontalCuts, h)
		maxVertSpace = getMaxSpace(verticalCuts, w)
		mod = 1000000000.0 + 7
		return int(maxHorSpace * maxVertSpace % mod)


class Solution:

	def getMax(self, max: int, cuts: List[int]) -> int:
		last = 0
		for x in cuts:
			cur = x - last
			if cur > max:
				max = cur
			last = x
		return max

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		mod = 1000000007
		horizontalCuts.sort()
		verticalCuts.sort()
		maxh = self.getMax(h - horizontalCuts[-1], horizontalCuts)
		maxv = self.getMax(w - verticalCuts[-1], verticalCuts)
		return maxh % mod * maxv % mod


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.append(0)
		horizontalCuts.append(h)
		verticalCuts.append(0)
		verticalCuts.append(w)
		horizontalCuts.sort()
		verticalCuts.sort()
		mw = 0
		mh = 0
		for (x, y) in zip(horizontalCuts, horizontalCuts[1:]):
			mw = max(mw, y - x)
		for (x, y) in zip(verticalCuts, verticalCuts[1:]):
			mh = max(mh, y - x)
		mod = 10 ** 9 + 7
		return mw * mh % mod


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		prev = 0
		hDiff = 0
		for horiz in horizontalCuts:
			hDiff = max(hDiff, horiz - prev)
			prev = horiz
		hDiff = max(h - prev, hDiff)
		prev = 0
		vDiff = 0
		for vert in verticalCuts:
			vDiff = max(vDiff, vert - prev)
			prev = vert
		vDiff = max(w - prev, vDiff)
		return vDiff * hDiff % (10 ** 9 + 7)


class Solution:

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

		def get_max_gap(array):
			array.sort()
			max_hor_width = array[0]
			for (previous_cut, next_cut) in zip(array, array[1:]):
				max_hor_width = max(max_hor_width, next_cut - previous_cut)
			return max_hor_width
		return get_max_gap(horizontalCuts) * get_max_gap(verticalCuts) % 1000000007


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		(max_h, max_w) = (max(horizontalCuts[0], h - horizontalCuts[-1]), max(verticalCuts[0], w - verticalCuts[-1]))
		for i in range(1, len(horizontalCuts)):
			max_h = max(max_h, horizontalCuts[i] - horizontalCuts[i - 1])
		for j in range(1, len(verticalCuts)):
			max_w = max(max_w, verticalCuts[j] - verticalCuts[j - 1])
		return max_w * max_h % (10 ** 9 + 7)


from typing import List
import numpy
import sys

class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.insert(0, 0)
		horizontalCuts.append(h)
		horizontalCuts.sort()
		verticalCuts.insert(0, 0)
		verticalCuts.append(w)
		verticalCuts.sort()
		maxh = -1
		maxv = -1
		for (index, value) in enumerate(horizontalCuts):
			if index == 0:
				continue
			maxh = max(maxh, value - horizontalCuts[index - 1])
		for (index, value) in enumerate(verticalCuts):
			if index == 0:
				continue
			maxv = max(maxv, value - verticalCuts[index - 1])
		module = int(pow(10, 9) + 7)
		result = maxv * maxh % module
		return result


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		mx = max(verticalCuts[0], w - verticalCuts[-1])
		my = max(horizontalCuts[0], h - horizontalCuts[-1])
		for i in range(1, len(verticalCuts)):
			mx = max(mx, verticalCuts[i] - verticalCuts[i - 1])
		for i in range(1, len(horizontalCuts)):
			my = max(my, horizontalCuts[i] - horizontalCuts[i - 1])
		return mx * my % (10 ** 9 + 7)


class Solution:

	def maxArea(self, h, w, horizontalCuts, verticalCuts):
		H = [0] + horizontalCuts + [h]
		W = [0] + verticalCuts + [w]
		H.sort()
		W.sort()
		(hmax, wmax) = (0, 0)
		for i in range(1, len(H)):
			hmax = max(hmax, H[i] - H[i - 1])
		for i in range(1, len(W)):
			wmax = max(wmax, W[i] - W[i - 1])
		return hmax * wmax % 1000000007


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		max_h = max(horizontalCuts[0], h - horizontalCuts[-1])
		if len(horizontalCuts) > 1:
			for i in range(len(horizontalCuts) - 1):
				if max_h < abs(horizontalCuts[i + 1] - horizontalCuts[i]):
					max_h = abs(horizontalCuts[i + 1] - horizontalCuts[i])
		max_v = max(verticalCuts[0], w - verticalCuts[-1])
		if len(verticalCuts) > 1:
			for i in range(len(verticalCuts) - 1):
				if max_v < abs(verticalCuts[i + 1] - verticalCuts[i]):
					max_v = abs(verticalCuts[i + 1] - verticalCuts[i])
		return max_h % (10 ** 9 + 7) * (max_v % (10 ** 9 + 7)) % (10 ** 9 + 7)


class Solution:

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

		def maxDelta(cuts, end):
			cuts.sort()
			cuts.append(end)
			cuts.append(0)
			md = 0
			for i in range(len(cuts) - 1):
				md = max(md, cuts[i] - cuts[i - 1])
			return md
		return maxDelta(horizontalCuts, h) * maxDelta(verticalCuts, w) % (10 ** 9 + 7)
		mh = maxDelta(horizontalCuts, h)
		mv = maxDelta(verticalCuts, w)
		return mh * mv % (10 ^ 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, hCuts: List[int], vCuts: List[int]) -> int:
		hCuts.sort()
		vCuts.sort()
		(H, V) = (max(hCuts[0], h - hCuts[-1]), max(vCuts[0], w - vCuts[-1]))
		for i in range(1, len(hCuts)):
			H = max(H, hCuts[i] - hCuts[i - 1])
		for i in range(1, len(vCuts)):
			V = max(V, vCuts[i] - vCuts[i - 1])
		return H * V % 1000000007


class Solution:

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

		def helper(ll, num):
			ll.append(num)
			ans = ll[0]
			for i in range(1, len(ll)):
				if ll[i] - ll[i - 1] > ans:
					ans = ll[i] - ll[i - 1]
			return ans
		return int(helper(horizontalCuts, h) * helper(verticalCuts, w) % (1000000000.0 + 7))


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts = [0] + sorted(horizontalCuts) + [h]
		verticalCuts = [0] + sorted(verticalCuts) + [w]
		new_h = max([horizontalCuts[i + 1] - horizontalCuts[i] for i in range(len(horizontalCuts) - 1)])
		new_w = max([verticalCuts[i + 1] - verticalCuts[i] for i in range(len(verticalCuts) - 1)])
		return new_h * new_w % (10 ** 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		modu = 1000000007
		h_max = 0
		v_max = 0
		horizontalCuts.append(0)
		horizontalCuts.append(h)
		verticalCuts.append(0)
		verticalCuts.append(w)
		horizontalCuts.sort()
		verticalCuts.sort()
		for i in range(1, len(horizontalCuts)):
			h_max = max(h_max, horizontalCuts[i] - horizontalCuts[i - 1])
		for j in range(1, len(verticalCuts)):
			v_max = max(v_max, verticalCuts[j] - verticalCuts[j - 1])
		return v_max * h_max % modu


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		max_h = horizontalCuts[0]
		for h_cut in range(1, len(horizontalCuts)):
			max_h = max(max_h, horizontalCuts[h_cut] - horizontalCuts[h_cut - 1])
		max_h = max(max_h, h - horizontalCuts[-1])
		max_v = verticalCuts[0]
		for v_cut in range(1, len(verticalCuts)):
			max_v = max(max_v, verticalCuts[v_cut] - verticalCuts[v_cut - 1])
		max_v = max(max_v, w - verticalCuts[-1])
		return max_h * max_v % int(1000000000.0 + 7)


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		max_hor_width = horizontalCuts[0]
		for i in range(len(horizontalCuts) - 1):
			max_hor_width = max(max_hor_width, horizontalCuts[i + 1] - horizontalCuts[i])
		max_hor_width = max(max_hor_width, h - horizontalCuts[len(horizontalCuts) - 1])
		max_vert_width = verticalCuts[0]
		for i in range(len(verticalCuts) - 1):
			max_vert_width = max(max_vert_width, verticalCuts[i + 1] - verticalCuts[i])
		max_vert_width = max(max_vert_width, w - verticalCuts[len(verticalCuts) - 1])
		return max_vert_width * max_hor_width % 1000000007


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		(ph, pw) = (0, 0)
		(msh, msw) = (0, 0)
		for ch in horizontalCuts:
			if ch - ph > msh:
				msh = ch - ph
			ph = ch
		if h - ph > msh:
			msh = h - ph
		for cw in verticalCuts:
			if cw - pw > msw:
				msw = cw - pw
			pw = cw
		if w - pw > msw:
			msw = w - pw
		return msh * msw % (10 ** 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		print(horizontalCuts, verticalCuts)
		pre = 0
		hori_max = 0
		for (i, cut) in enumerate(horizontalCuts):
			hori_max = max(hori_max, cut - pre)
			pre = cut
		hori_max = max(hori_max, h - pre)
		pre = 0
		vert_max = 0
		for (i, cut) in enumerate(verticalCuts):
			vert_max = max(vert_max, cut - pre)
			pre = cut
		vert_max = max(vert_max, w - pre)
		return hori_max * vert_max % (10 ** 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		ver = [0] + sorted(verticalCuts) + [w]
		hor = [0] + sorted(horizontalCuts) + [h]
		dh = max((hor[i] - hor[i - 1] for i in range(1, len(hor))))
		dv = max((ver[i] - ver[i - 1] for i in range(1, len(ver))))
		return dh * dv % (10 ** 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.append(0)
		horizontalCuts.append(h)
		horizontalCuts.sort()
		Maxh = max([horizontalCuts[i] - horizontalCuts[i - 1] for i in range(1, len(horizontalCuts))])
		verticalCuts.append(0)
		verticalCuts.append(w)
		verticalCuts.sort()
		Maxv = max([verticalCuts[i] - verticalCuts[i - 1] for i in range(1, len(verticalCuts))])
		return Maxh * Maxv % 1000000007


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		(horizontalCuts, verticalCuts) = (sorted([0, h] + horizontalCuts), sorted([0, w] + verticalCuts))
		return max([after - prev for (after, prev) in zip(horizontalCuts[1:], horizontalCuts)]) * max([after - prev for (after, prev) in zip(verticalCuts[1:], verticalCuts)]) % (10 ** 9 + 7)


class Solution:

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

		def maxDelta(cuts, end):
			cuts.sort()
			cuts.append(end)
			cuts.append(0)
			md = 0
			for i in range(len(cuts) - 1):
				md = max(md, cuts[i] - cuts[i - 1])
			return md

		def getGap(arr, n):
			prev = 0
			i = 0
			res = 0
			while i < len(arr):
				res = max(arr[i] - prev, res)
				prev = arr[i]
				i += 1
			return max(n - prev, res)
		return maxDelta(horizontalCuts, h) * maxDelta(verticalCuts, w) % (10 ** 9 + 7)
		mh = maxDelta(horizontalCuts, h)
		mv = maxDelta(verticalCuts, w)
		return mh * mv % (10 ^ 9 + 7)


class Solution:

	def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
		horizontalCuts.sort()
		verticalCuts.sort()
		hr = [0] + horizontalCuts + [h]
		vr = [0] + verticalCuts + [w]
		(hmax, vmax) = (0, 0)
		for i in range(1, len(hr)):
			hmax = max(hmax, hr[i] - hr[i - 1])
		for i in range(1, len(vr)):
			vmax = max(vmax, vr[i] - vr[i - 1])
		return hmax * vmax % (10 ** 9 + 7)