Greedy | Detailed Explanation | With complexity analysis | Python
We need to find the largest area we can make, given the horizontal and vertical cuts.\n\nArea = width * height\n\nWe can break the solution into 2 parts: findin
We need to find the largest area we can make, given the horizontal and vertical cuts.\n\n`Area = width * height`\n\nWe can break the solution into 2 parts: finding the largest **horizontal distance** `horizontalCuts[i] - horizontalCuts[j]` such that it is maximized, and finding the **largest vertical distance** verticalCuts[i] - verticalCuts[j] such that it is maximized.\n\nThen we will multiply them to form the **largest area.**\n\nWe can do this because we know that vertical and horizontal lines are **independent**. The vertical lines will cross the horizontal lines across the whole Y axis, and vice versa.\n\nNow to find the largest distance for each of the axis we can simply compare `horizontalCuts[i] - horizontalCuts[i-1]` if the array is sorted, because comparing with non-adjacent lines will make invalid cuts, since there will be lines in the middle of the two lines.\n\nSame for `verticalCuts[i] - verticalCuts[i-1]`\n\n# Code\n```\nclass Solution:\n    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n\t\t# We need to append 0 and h to horizontalCuts, since they are a line too\n        horizontalCuts.append(0)\n        horizontalCuts.append(h)\n        \n\t\t# We need to append 0 and w to verticalCuts, since they are a line too\n        verticalCuts.append(0)\n        verticalCuts.append(w)\n        \n\t\t# Sort in order to compare adjacent lines\n        horizontalCuts.sort()\n        verticalCuts.sort()\n        \n        best_vertical_distance = 0\n        best_horizontal_distance = 0\n        \n\t\t# Find largest vertical distance\n        for vertical_index in range(1, len(verticalCuts)):\n            vertical_distance_between_adjacent = verticalCuts[vertical_index] - verticalCuts[vertical_index - 1]\n            best_vertical_distance = max(best_vertical_distance, vertical_distance_between_adjacent)\n    \n\t\t# find largest horizontal distance\n        for horizontal_index in range(1, len(horizontalCuts)):\n            horizontal_distance_between_adjacent = horizontalCuts[horizontal_index] - horizontalCuts[horizontal_index - 1]\n            best_horizontal_distance = max(best_horizontal_distance, horizontal_distance_between_adjacent)\n            \n        \n\t\t# multiply the distances. Don\'t forget the mod\n        return (best_vertical_distance * best_horizontal_distance) % (pow(10, 9) + 7)\n```\n\n# Complexity analysis\nLet horizontalCuts be `n`, and verticalCuts be `m`\n\n* Time - O(nlogn + mlogm) - We sort both the arrays, and then traverse them. Sorting is the most expensive operation here.\n* Space - O(logn + logm) - If we sort with nlogn time, the divide and conquer algorithm takes `logn` space complexity.
['Python']