My Thought Process 🤌
This solution is merely an explanation of how i thought of solving the problem (or how i wished to solve problem)\n\nQuestion right off the back gives you feeli
**This solution is merely an explanation of how i thought of solving the problem (or how i wished to solve problem)**\n\nQuestion right off the back gives you feeling of that we will have to find a greedy solution, but the question is how do we know that it is for sure is a greedy problem.\n\n**1. contraints are perticularly large**\n\n2 <= h, w <= 10^9\n1 <= horizontalCuts.length <= min(h - 1, 10^5)\n1 <= verticalCuts.length <= min(w - 1, 10^5)\n\nIf you notice contraint quite carefully for length of arrays ( number of cuts , horizontally and vertically ) then at most there could be 10^5 cuts possible. and if you have done a good amount of questions then this will give you hint that a brute force solution won\'t work ( even a solution with O(n^2) wont work ). \n\n***but what exactly would be a brute force solution for this problem ?***\nwe could argue that for each horizontal cut we will have to calculate the size of cake that make with respect to all the vertical cuts present. i.e for h1 we will have to calculate area in (orange,blue, voilet) and keep track of maximum all the time.\n*Repeating this for all the horizontal cuts, we will get the area in green as your answer (maximum area)*\n![image](https://assets.leetcode.com/users/images/c081d7fa-df02-4963-8548-f6ee23d7c866_1656757135.7729135.png)\n\n**Second intituition:**\nAs i said earlier as well that, this question is probably screeming to be done in greedy manner. and right of the back one can come up with an hypothesis ( and correct argument) that horizontal cuts with longest distance between them would make the the largest area and that too with widest vertical cuts.\n\n*At this point you could write a well written and correct code. but you missed a very crucial step here as well*\n***how do you know that this hypothesis is certainily correct ?***\n\n**1st Thought for prooving our hypothesis**\nIf You look closely than these cuts are nothing but parllel lines and are perpendicular to the other ones. and if you consider them long enough ( extend them to infinity), then you could make a mathematically correct argument that *two widest vertical cuts i.e vertical cuts with maximum distance b/w them*  and *two horizontal cuts with maximum height distance b/w them* are sure to intersect each other and surely this area formed b/w would be the largest one.\n\n![image](https://assets.leetcode.com/users/images/981e6a05-c809-4eea-b377-8fd09196fda0_1656758080.2442498.png)\n\n**2nd Thought for prooving our hypothesis**\nSecond proof is slightly mathematical in nature, i.e proof by contradiction. we could start with a alternative hypothesis that the largest area would not lie b/w horizontal cuts with highest distance b/w them and hence with area of ***hi * wi*** but we could see this hypothesis getting wrong as soon as we compare it with area where both the **h** and **w** are widest.  ( i havn\'t explained it entirely, but i am sure that you would be able to derive it with little effort)\n\n**Code**\n```\nclass Solution {\npublic:\n    int mod = 1\'000\'000\'007;\n    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {\n        int n = horizontalCuts.size(),m = verticalCuts.size();\n        \n        sort(horizontalCuts.begin(),horizontalCuts.end());\n        sort(verticalCuts.begin(),verticalCuts.end());\n        \n        auto maxVerticalDis =INT_MIN,maxHorizontalDis=INT_MIN;\n        \n        for(int i=0;i<n;++i){\n            if(i==0)\n                maxVerticalDis = max(maxVerticalDis,horizontalCuts[i]);\n            else\n                maxVerticalDis = max(maxVerticalDis,horizontalCuts[i] - horizontalCuts[i-1]);\n        }\n        \n        maxVerticalDis = max(maxVerticalDis,h-horizontalCuts[n-1]);\n        \n        for(int i=0;i<m;++i){\n            if(i==0)\n                maxHorizontalDis = max(maxHorizontalDis,verticalCuts[i]);\n            else\n                maxHorizontalDis = max(maxHorizontalDis,verticalCuts[i] - verticalCuts[i-1]);\n        }\n        \n        maxHorizontalDis = max(maxHorizontalDis,w-verticalCuts[m-1]);\n        \n        return (long) maxHorizontalDis*maxVerticalDis%mod;\n    }\n};\n```\n\n**Hope You liked it , if it helped please upvote**
['Greedy', 'C++']