Problem

You are given a rectangular cake of size h x 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, and
  • 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 large number, return this modulo 10^9 + 7.

Examples

Example 1:

1
2
3

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:

1
2
3

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:

1
2

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

Constraints

  • All the elements in horizontalCuts are distinct.
  • All the elements in verticalCuts are distinct.

Solution

Method 1 - Sort the Cuts and the Calculate Each Max Area

As the cuts are are not ordered, we must sort them. THen we just loop on individual cuts and check for max area.

Algo

  • Sort both horizontalCuts and verticalCuts.
  • For horizontal cuts, find the largest gap by comparing the first cut, the distance from the last cut to the edge, and all gaps between consecutive cuts.
  • Repeat this process for vertical cuts to get the maximum width.
  • Multiply the maximum height and width, convert to long to avoid overflow, and return the result modulo 10^9 + 7.

Code

Method 1 – Sorting and Gap Calculation

Intuition

The largest piece of cake will be determined by the largest gap between consecutive horizontal cuts (height) and the largest gap between consecutive vertical cuts (width). By sorting the cuts and checking the maximum difference between adjacent cuts (including the edges), we can easily find these values.

Approach

  • Sort both horizontalCuts and verticalCuts.
  • For horizontal cuts, find the largest gap by comparing the first cut, the distance from the last cut to the edge, and all gaps between consecutive cuts.
  • Repeat this process for vertical cuts to get the maximum width.
  • Multiply the maximum height and width, convert to long to avoid overflow, and return the result modulo 10^9 + 7.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
	int maxArea(int h, int w, vector<int>& hc, vector<int>& vc) {
		int M = 1e9 + 7;
		sort(hc.begin(), hc.end());
		sort(vc.begin(), vc.end());
		int max_h = max(hc[0], h - hc.back());
		int max_w = max(vc[0], w - vc.back());
		for (int i = 1; i < hc.size(); ++i)
			max_h = max(max_h, hc[i] - hc[i - 1]);
		for (int i = 1; i < vc.size(); ++i)
			max_w = max(max_w, vc[i] - vc[i - 1]);
		long long ans = 1LL * max_h * max_w;
		return ans % M;
	}
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func maxArea(h int, w int, hc []int, vc []int) int {
	M := int(1e9 + 7)
	sort.Ints(hc)
	sort.Ints(vc)
	maxH := max(hc[0], h-hc[len(hc)-1])
	maxW := max(vc[0], w-vc[len(vc)-1])
	for i := 1; i < len(hc); i++ {
		if hc[i]-hc[i-1] > maxH {
			maxH = hc[i] - hc[i-1]
		}
	}
	for i := 1; i < len(vc); i++ {
		if vc[i]-vc[i-1] > maxW {
			maxW = vc[i] - vc[i-1]
		}
	}
	return (maxH * maxW) % M
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
	public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
				final int M = (int) Math.pow(10, 9) + 7;
		Arrays.sort(horizontalCuts);
		Arrays.sort(verticalCuts);
	
		int m = horizontalCuts.length;
		int n = verticalCuts.length;
		
		int maxH = Math.max(horizontalCuts[0] - 0, h - horizontalCuts[m - 1]);
		int maxW = Math.max(verticalCuts[0] - 0, w - verticalCuts[n - 1]);
	
		for (int i = 1; i < m; i++) {
			maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i - 1]);
		}
		for (int i = 1; i < n; i++) {
			maxW = Math.max(maxW, verticalCuts[i] - verticalCuts[i - 1]);
		}
	
		return (int) ((long) maxH * maxW % M);
	}
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	fun maxArea(h: Int, w: Int, hc: IntArray, vc: IntArray): Int {
		val M = 1_000_000_007
		hc.sort()
		vc.sort()
		var maxH = maxOf(hc[0], h - hc.last())
		var maxW = maxOf(vc[0], w - vc.last())
		for (i in 1 until hc.size) {
			maxH = maxOf(maxH, hc[i] - hc[i - 1])
		}
		for (i in 1 until vc.size) {
			maxW = maxOf(maxW, vc[i] - vc[i - 1])
		}
		return ((maxH.toLong() * maxW) % M).toInt()
	}
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
	def maxArea(self, h: int, w: int, horizontalCuts: list[int], verticalCuts: list[int]) -> int:
		M = 10**9 + 7
		horizontalCuts.sort()
		verticalCuts.sort()
		max_h = max(horizontalCuts[0], h - horizontalCuts[-1])
		max_w = max(verticalCuts[0], w - verticalCuts[-1])
		for i in range(1, len(horizontalCuts)):
			max_h = max(max_h, horizontalCuts[i] - horizontalCuts[i - 1])
		for i in range(1, len(verticalCuts)):
			max_w = max(max_w, verticalCuts[i] - verticalCuts[i - 1])
		return (max_h * max_w) % M
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
	pub fn max_area(h: i32, w: i32, mut hc: Vec<i32>, mut vc: Vec<i32>) -> i32 {
		let m = 1_000_000_007;
		hc.sort();
		vc.sort();
		let mut max_h = hc[0].max(h - hc[hc.len() - 1]);
		let mut max_w = vc[0].max(w - vc[vc.len() - 1]);
		for i in 1..hc.len() {
			max_h = max_h.max(hc[i] - hc[i - 1]);
		}
		for i in 1..vc.len() {
			max_w = max_w.max(vc[i] - vc[i - 1]);
		}
		((max_h as i64 * max_w as i64) % m) as i32
	}
}

Complexity

  • ⏰ Time complexity: O(m log m + n log n), where m and n are the lengths of horizontalCuts and verticalCuts.
  • 🧺 Space complexity: O(1), (ignoring the space used by sorting, as it can be done in-place).