Intuitive Explanation with Clean Modularized Code
Be sure to upvote if you thought this was a good explanation!\n\nJoin our discord to be part of an interview prep community!\nhttps://discord.gg/7wpQQFYC\n\nInt
Be sure to **upvote** if you thought this was a good explanation!\n\nJoin our discord to be part of an interview prep community!\n**https://discord.gg/7wpQQFYC**\n\n**Intuition**\nThe key insight here is that not all horizontal and vertical cuts matter. The area of a rectangle is `width * height`. To maximize this expression, we need to maximize the `width` and `height` between any two cuts.\n\nSince the horizontal and vertical cuts are independent, we can find the `maxHeight` between any two adjacent horizontal cuts, and `maxWidth` between any adjacent two vertical cuts separately. The cuts extend through the entire cake, so we will always be able to find a rectangle with height `maxHeight` and width `maxWidth`. The max area is then `maxHeight * maxWidth`.\n\n**Implementation**\n1. Append `0` and `h` to `horizontalCuts` since they effectively act as "cuts" in an infinite sized cake.\n2. Sort the `horizontalCuts` so that adjacent cuts are next to each other.\n3. Find `maxHeight` by looping through each pair of adjacent horizontal cuts and calculating their distance.\n4. Repeat steps 1-3 for `verticalCuts`. Since there is repeated logic here, let\'s make use of a helper function called `calcMaxDist`!\n5. Calculate `maxArea` as `(maxHeight * maxWidth) % (10**9 + 7)`.\n\n**Python**\n```python\nclass Solution:\n    def calcMaxDist(self, cuts, end):\n        cuts.append(0)\n        cuts.append(end)\n        cuts.sort()\n        return max(cuts[i] - cuts[i - 1] for i in range(1, len(cuts)))\n        \n    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        maxWidth = self.calcMaxDist(horizontalCuts, h)\n        maxHeight = self.calcMaxDist(verticalCuts, w)\n        return (maxWidth * maxHeight) % MOD\n```\n\n**C++**\n```c++\nclass Solution {\n    int calcMaxDist(vector<int>& cuts, int end) {\n        cuts.push_back(0);\n        cuts.push_back(end);\n        sort(cuts.begin(), cuts.end());\n        int dist = 0;\n        for (int i = 1; i < cuts.size(); i++) {\n            dist = max(dist, cuts[i] - cuts[i - 1]);\n        }\n        return dist;\n    }\n    \npublic:\n    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {\n        const int MOD = 1e9 + 7;\n        int maxHeight = calcMaxDist(horizontalCuts, h);\n        int maxWidth = calcMaxDist(verticalCuts, w);\n        int area = (int) ((long long) maxWidth * maxHeight % MOD);\n        return area;\n    }\n};\n```\n\n**Time Complexity**: O(nlogn + mlogm) - Sorting an array of length `n` costs `nlogn`. We sort both arrays so both sorting times need to be factored in to the overall complexity. Although we also iterate through both arrays, which costs O(n) and O(m) time, these iterations get dominated by sorting in time complexity analysis.\n**Space Complexity**: O(1) - Regardless of the input size, we only ever need to initialize a constant number of new variables.\n\nJoin our discord to discuss this problem and prepare for interviews with other people!\n**https://discord.gg/7wpQQFYC**
['C', 'Sorting', 'Python', 'C++']