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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1575

Difficulty: Medium

Paid? No

Companies: IXL, BNY Mellon

Problem Description

Given a rectangular cake of dimensions h x w, and two arrays horizontalCuts and verticalCuts indicating where to cut the cake horizontally and vertically, determine the maximum area of any piece of cake after performing all cuts. The answer should be returned modulo 10^9 + 7.

Key Insights

  • Sort the horizontalCuts and verticalCuts arrays to handle adjacent sections.
  • Include the boundaries (0 and h for horizontal, 0 and w for vertical) to properly calculate edge segment lengths.
  • Determine the maximum gap between consecutive cuts in horizontal and vertical directions.
  • Multiply the maximum horizontal gap by the maximum vertical gap to get the largest piece of cake.
  • Use modulo arithmetic to manage large numbers per the problem specification.

Space and Time Complexity

Time Complexity: O(m log m + n log n) where m is the length of horizontalCuts and n is the length of verticalCuts (due to sorting). Space Complexity: O(1) additional space if sorting is done in-place (ignoring input storage).

Solution

The algorithm begins by sorting the horizontalCuts and verticalCuts arrays. To account for the edges, compute the difference between the first cut and the cake’s start (0) and the difference between the last cut and the cake’s end (h for horizontal, w for vertical). Then, calculate the maximum gap between consecutive cuts. The maximum area is the product of the largest horizontal gap and the largest vertical gap, taken modulo 10^9 + 7 to handle large numbers. The solution uses sorting and simple linear traversals, making it efficient for the input constraints.

Code Solutions

# Python solution with line-by-line comments

MOD = 10**9 + 7

def maxArea(h, w, horizontalCuts, verticalCuts):
    # Sort the arrays to process cuts in order
    horizontalCuts.sort()
    verticalCuts.sort()
    
    # Calculate maximum gap for horizontal cuts.
    max_h_gap = max(horizontalCuts[0], h - horizontalCuts[-1])
    for i in range(1, len(horizontalCuts)):
        # Gap between two consecutive horizontal cuts
        current_gap = horizontalCuts[i] - horizontalCuts[i - 1]
        max_h_gap = max(max_h_gap, current_gap)
    
    # Calculate maximum gap for vertical cuts.
    max_v_gap = max(verticalCuts[0], w - verticalCuts[-1])
    for j in range(1, len(verticalCuts)):
        # Gap between two consecutive vertical cuts
        current_gap = verticalCuts[j] - verticalCuts[j - 1]
        max_v_gap = max(max_v_gap, current_gap)
    
    # Calculate the maximum area modulo 10^9 + 7
    return (max_h_gap * max_v_gap) % MOD

# Example usage:
print(maxArea(5, 4, [1,2,4], [1,3]))  # Should output 4
← Back to All Questions