✅ Short & Easy w/ Explanation | Find Max Gap between Cuts | Beats 100%
\u2714\uFE0F Solution (Sort & Find Max Gaps)\n\nWe are required to find the maximum area of a piece of cake after applying the cuts. It should be obvious that m
\u2714\uFE0F ***Solution (Sort & Find Max Gaps)***\n\nWe are required to find the maximum area of a piece of cake after applying the cuts. It should be obvious that maximum area in a rectangle can be obtained by maximizing its height and width.\n\nSo, we just need to maximize the height and width of a piece of cake. For this, just **sort the cuts** and iterate through them to **get the maximum gap between two consecutive cuts**. It\'s better to consider the case of length of piece before the first cut and after the last cut separately outside the loop just to keep the loop simple.\n\n\n**C++**\n```\nint maxArea(int h, int w, vector<int>& H, vector<int>& V) {\n\treturn long(getMaxGap(H, h)) * getMaxGap(V, w) % 1000000007;\n}\nint getMaxGap(vector<int>& nums, int max_size) {\n\tsort(begin(nums), end(nums));\n\tint maxGap = max(nums[0], max_size - nums.back()); // handling the case of first and last piece of cake\n\tfor(int i = 1; i < size(nums); i++) maxGap = max(maxGap, nums[i] - nums[i - 1]);\n\treturn maxGap;\n}\n```\n\n---\n\n**Python**\n```\ndef maxArea(self, h: int, w: int, H: List[int], V: List[int]) -> int:\n\tdef getMaxGap(nums, max_size):\n\t\tmaxGap = max(nums[0], max_size - nums[-1])\n\t\tfor i in range(1, len(nums)):\n\t\t\tmaxGap = max(maxGap, nums[i] - nums[i - 1])\n\t\treturn maxGap\n\treturn getMaxGap(sorted(H), h) * getMaxGap(sorted(V), w) % 1000000007\n```\n\n***Time Complexity :*** **`O(HlogH + VlogV)`**, where *`H`* is the number of Horizontal cuts and *`V`* is the number of Vertical cuts\n***Space Complexity :*** **`O(1)`**, we don\'t use any extra space (ignoring the space required for sort)\n\n---\n\n*Best Runtime*\n<table><tr><td><img src=https://assets.leetcode.com/users/images/dd4c751c-3516-414a-b300-747f3b2f7932_1622708467.533695.png /></td></tr></table>\n\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C', 'Python']