Python3 O(N log(N)) divide and conquer approach explained
The first approach I came up with was to try every possible pair of start and end positions, keeping track of the minimum encountered height since the correspon
The first approach I came up with was to try every possible pair of start and end positions, keeping track of the minimum encountered height since the corresponding starting position and pick the pair achieving maximum area. This can be implemented in O(N^2) time complexity. This approach exceeded the time limit (at least my Python3 implementation).\n\nI could not come up with an O(N) solution at the time. So decided to implement a divide and conquer recursive solution inspired by [this solution](https://leetcode.com/problems/maximum-subarray/discuss/561773/Divide-and-conquer-solution) to the follow up of the Maximum Subarray problem.\n\nWe take the full array and split it in half, the maximum Area achievable by the array is the largest of :\n*  The maximum area achievable in the left half alone\n*  The maximum area achievable in the right half alone\n*  The maximum area achievable by combining both halves (in this case, we look at rectangles covering at least one bar from each half, anything else is already taken into account by the first two bullet points)\n\nThe first two points can be calculated in the same way recursively, with the base case of the recursion being a sub-array with one element.\nThe third one can be calculated in linear time. Start with the right most element in the left half and left most element in the right half (as said before we need at least one element from each half). And then add the bars one by one from the left or from the right, depending on which one is higher, until the boundaries of the subarray are reached. In the process, keep track of the minimum encountered height and of the largest obtained area.\n\nThe time complexity of this subroutine is linear and the overall complexity is O(N log(N)), since there are log(N) recursion depth levels and the subroutine is called 2^x times on subarrays of length N/2^x on each such level, where x is the level number, and the call on the full array is at level 0. \n\n```\nclass Solution:\n    def largestRectangleArea(self, heights: List[int]) -> int:\n        if len(heights) == 0:\n            return 0\n        self.heights = heights\n        return self.largestArea(0, len(heights) - 1)\n    \n    def largestArea(self, l, r):\n        if l == r:\n            return self.heights[l]\n        mid = (l + r) // 2\n        leftArea = self.largestArea(l, mid)\n        rightArea = self.largestArea(mid + 1, r)\n        crossArea = self.crossLargestArea(l, mid, r)\n        return max(leftArea, rightArea, crossArea)\n    \n    def crossLargestArea(self, l, mid, r):\n        minH = min(self.heights[mid], self.heights[mid + 1])\n        maxArea = 2 * minH\n        i = mid\n        j = mid + 1\n        while i > l or j < r:\n            if i <= l:\n                j += 1\n                minH = min(minH, self.heights[j])\n                maxArea = max(maxArea, (j - l + 1) * minH)\n            elif j >= r:\n                i -= 1\n                minH = min(minH, self.heights[i])\n                maxArea = max(maxArea, (r - i + 1) * minH)\n            elif self.heights[i - 1] > self.heights[j + 1]:\n                i -= 1\n                minH = min(minH, self.heights[i])\n                maxArea = max(maxArea, (j - i + 1) * minH)\n            else:\n                j += 1\n                minH = min(minH, self.heights[j])\n                maxArea = max(maxArea, (j - i + 1) * minH)\n        return maxArea\n```
['Divide and Conquer', 'Python3']