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

Problem

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.

Problem Summary

The rectangular cake has height h and width w. You are given two integer arrays, horizontalCuts and verticalCuts, where horizontalCuts[i] is the distance from the top of the rectangular cake to the i-th horizontal cut. Similarly, verticalCuts[j] is the distance from the left side of the rectangular cake to the j-th vertical cut. After cutting at the horizontal and vertical positions provided in the arrays horizontalCuts and verticalCuts, find the piece of cake with the maximum area and return its area. Since the answer may be a very large number, return the result modulo 10^9 + 7.

Solution Ideas

• After reading the problem, it is relatively easy to come up with the solution. Find the maximum difference between horizontal cuts and the maximum difference between vertical cuts; the rectangle formed by these 4 sides is the maximum rectangle. However, there are special cases to consider. In addition to the cut coordinates given by the problem, there are 4 default cuts, namely the original 4 edges of the cake. As shown in the second figure below, the largest rectangle is actually outside the given cuts. Therefore, when finding the maximum difference between horizontal cuts and the maximum difference between vertical cuts, the original 4 edges of the cake need to be considered.

Code

package leetcode

import "sort"

func maxArea(h int, w int, hcuts []int, vcuts []int) int {
	sort.Ints(hcuts)
	sort.Ints(vcuts)
	maxw, maxl := hcuts[0], vcuts[0]
	for i, c := range hcuts[1:] {
		if c-hcuts[i] > maxw {
			maxw = c - hcuts[i]
		}
	}
	if h-hcuts[len(hcuts)-1] > maxw {
		maxw = h - hcuts[len(hcuts)-1]
	}
	for i, c := range vcuts[1:] {
		if c-vcuts[i] > maxl {
			maxl = c - vcuts[i]
		}
	}
	if w-vcuts[len(vcuts)-1] > maxl {
		maxl = w - vcuts[len(vcuts)-1]
	}
	return (maxw * maxl) % (1000000007)
}