We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts. The goal is to return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays. Since the answer can be a large number, return this modulo 10^9 + 7.

Key Insights

  • The maximum area of a piece of cake is determined by the largest segments created by horizontal and vertical cuts.
  • To find the maximum height of the cake, calculate the maximum distance between consecutive horizontal cuts.
  • To find the maximum width of the cake, calculate the maximum distance between consecutive vertical cuts.
  • The area can be computed by multiplying the maximum height and maximum width.

Space and Time Complexity

Time Complexity: O(n log n + m log m), where n is the number of horizontal cuts and m is the number of vertical cuts due to sorting. Space Complexity: O(1), as we only use a few additional variables for computations.

Solution

The solution uses sorting to arrange the cut positions and then calculates the maximum height and width of the cake pieces. The algorithm can be summarized as follows:

  1. Sort the horizontalCuts and verticalCuts arrays.
  2. Calculate the maximum height by finding the largest difference between consecutive horizontal cuts and the edges of the cake.
  3. Calculate the maximum width in a similar manner for vertical cuts.
  4. The final area is the product of the maximum height and width, taken modulo 10^9 + 7.

Code Solutions

def maxArea(h, w, horizontalCuts, verticalCuts):
    horizontalCuts.sort()
    verticalCuts.sort()
    
    # Calculate max height
    max_height = max(horizontalCuts[0], h - horizontalCuts[-1])
    for i in range(1, len(horizontalCuts)):
        max_height = max(max_height, horizontalCuts[i] - horizontalCuts[i - 1])
    
    # Calculate max width
    max_width = max(verticalCuts[0], w - verticalCuts[-1])
    for i in range(1, len(verticalCuts)):
        max_width = max(max_width, verticalCuts[i] - verticalCuts[i - 1])
    
    # Calculate the maximum area
    return (max_height * max_width) % (10**9 + 7)
← Back to All Questions