Previous Next

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

TCS NQT Coding Easy

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.
  • 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. Since the answer can be a large number, return it modulo 109 + 7.

Examples:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]

Output: 4

Explanation: The figure represents the given rectangular cake. Red lines are the cuts. The green piece has the maximum area of 4.

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

Output: 6

Explanation: The figure represents the given rectangular cake. Red lines are the cuts. The green and yellow pieces have the maximum area of 6.

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

Output: 9

Explanation: The figure represents the given rectangular cake. Red lines are the cuts. The largest piece has an area of 9.

Constraints

  • 2 <= h, w <= 109
  • 1 <= horizontalCuts.length <= min(h - 1, 105)
  • 1 <= verticalCuts.length <= min(w - 1, 105)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[j] < w
  • All elements in horizontalCuts are distinct.
  • All elements in verticalCuts are distinct.