[C++] Max gaps product - buckets and the pigeonhole principle - O(n)
Although the most intuitive approach would be to simply sort the cuts and find the product of the max gaps in both vertical and horizontal cuts which takes O(N 
Although the most intuitive approach would be to simply sort the cuts and find the product of the max gaps in both vertical and horizontal cuts which takes **O(N log(n) + M log(m))** time complexity and **O(1)** additional memory like this one:\n\n```cpp\nconst int MOD = 1e9 + 7;\n\nclass Solution {\npublic:\n    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {\n        long int ans = 0, maxWidth = 0, maxHeight = 0;\n        \n        horizontalCuts.push_back(h);\n        verticalCuts.push_back(w);\n        \n        sort(begin(horizontalCuts), end(horizontalCuts));\n        sort(begin(verticalCuts), end(verticalCuts));\n        \n        for (int i = 0, prev = 0; i < horizontalCuts.size(); i++) {\n            maxHeight = max(maxHeight, (long int) horizontalCuts[i] - prev);\n            prev = horizontalCuts[i];\n        }\n        \n        for (int i = 0, prev = 0; i < verticalCuts.size(); i++) {\n            maxWidth = max(maxWidth, (long int) verticalCuts[i] - prev);\n            prev = verticalCuts[i];\n        }\n        \n        return (maxWidth * maxHeight) % MOD;\n    }\n};\n```\n\nwe could further expand the idea and rely on the [Pigeonhole Principle](https://en.wikipedia.org/wiki/Pigeonhole_principle) and slightly modified bucket sort algorithm from [164. Maximum Gap (Hard)](https://leetcode.com/problems/maximum-gap/). This takes us only **O(n + m)** time complexity and additional **O(max(m, n))** space complexity:\n\n```cpp\nconst int MOD = 1e9 + 7;\n\nclass Solution {\npublic:\n    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {\n        long int maxHeight = getMaxGap(horizontalCuts, h),\n            maxWidth = getMaxGap(verticalCuts, w);\n        \n        return (maxWidth * maxHeight) % MOD;\n    }\n    \n    int getMaxGap(const vector<int>& cuts, const int size) {\n        int minCut = *min_element(begin(cuts), end(cuts)),\n            maxCut = *max_element(begin(cuts), end(cuts));\n        int bucketSize = max(1, (maxCut - minCut) / (int) cuts.size()),\n            prevBucketMax = minCut,\n            ans = max(minCut, size - maxCut);\n        vector<tuple<bool, int, int>> buckets((maxCut - minCut) / bucketSize + 1, {false, INT_MAX, INT_MIN});\n        \n        for (const int& cut: cuts) {\n            int bucketIdx = (cut - minCut) / bucketSize;\n            \n            get<0>(buckets[bucketIdx]) = true;\n            get<1>(buckets[bucketIdx]) = min(get<1>(buckets[bucketIdx]), cut);\n            get<2>(buckets[bucketIdx]) = max(get<2>(buckets[bucketIdx]), cut);\n        }\n        \n        for (auto &[used, bucketMin, bucketMax]: buckets) {\n            if (not used) {\n                continue;\n            }\n            \n            ans = max(ans, bucketMin - prevBucketMax);\n            prevBucketMax = bucketMax;\n        }\n\n        return ans;\n    }\n};\n```\n\n![image](https://assets.leetcode.com/users/images/61949648-471d-43e3-a91e-e14c28ac479c_1622721968.4887948.png)\n
['C', 'Bucket Sort', 'C++']