C++ || O(N) || Easy to Understand with In-Depth Explanation and Examples
Table of Contents\n\n- TL;DR\n  - Code\n  - Complexity\n- In Depth Analysis\n  - Intuition\n  - Approach\n  - Example\n\n# TL;DR\n\nPrecompute the next smallest
#### Table of Contents\n\n- [TL;DR](#tldr)\n  - [Code](#code)\n  - [Complexity](#complexity)\n- [In Depth Analysis](#in-depth-analysis)\n  - [Intuition](#intuition)\n  - [Approach](#approach)\n  - [Example](#example)\n\n# TL;DR\n\nPrecompute the next smallest height for every height going from left to right and also from right to left. Then, we can go through these arrays and compute the largest area by finding the next smallest bar from left to right to determine the width and multiply it by the height of itself.\n\n## Code\n\n```c++\ntypedef long long ll;\n\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        const int n = heights.size();\n        ll ans = 0;\n\n        stack<int> elems;\n        vector<int> next_smallest_height_to_left(n, -1),\n                    next_smallest_height_to_right(n, n);\n\n        for (int i = 0; i < n; i++) {\n            while (!elems.empty() && heights[elems.top()] > heights[i]) {\n                next_smallest_height_to_right[elems.top()] = i;\n                elems.pop();\n            }\n            elems.push(i);\n        }\n\n        // This is done because stack does not have a clear function\n        while (!elems.empty()) elems.pop();\n\n        for (int i = n - 1; i >= 0; i--) {\n            while (!elems.empty() && heights[elems.top()] > heights[i]) {\n                next_smallest_height_to_left[elems.top()] = i;\n                elems.pop();\n            }\n            elems.push(i);\n        }\n\n        for (int i = 0; i < n; i++) {\n            int width = next_smallest_height_to_right[i] - next_smallest_height_to_left[i] - 1;\n            ans = max(ans, 1LL * width * heights[i]);\n        }\n\n        return ans;\n    }\n};\n```\n\n## Complexity\n\n**Time Complexity:** $$O(N)$$ where $$N$$ is the length of the input array\n**Space Complexity:** $$O(N)$$\n\n**PLEASE UPVOTE IF YOU FIND MY POST HELPFUL!! \uD83E\uDD7A\uD83D\uDE01**\n\n---\n\n# In Depth Analysis\n\n## Intuition\n\nWe want to keep track of the next smallest height for each bar going from left to right and right to left, which we can precompute using a stack. When we have this, we know that for any given point that the way to figure out its area is finding the distance between the smallest value to the left of it and the smallest value to the right of it to give us the horizontal width of the rectangle and multiplying that by the height of the actual bar itself.\n\nFor example, take `[2,1,5,6,2,3]` as the heights. For index 0, the smallest value to the left of it is index -1 (since it doesn\'t exist, pretend the height is 0) and the smallest value to the right of it is at index 1 (height of 1). Then to find the distance it is 1 - (- 1) - 1 = 1 which is the correct width for the rectangle of this height. Then we multiply the height (2) times the width to get that with index 0, we can get a rectangle of area 2. If you are confused, take a look at the [bottom](#example) for a full walkthrough with this example\n\n## Approach \n\nUse 2 vectors: one to hold the index of the next smallest value to the left and the other one for the smallest value to the right. We can populate these arrays by using a stack and keeping it monotonically increasing. For finding the smallest height to the right,the way we do that is if the index at the top of the stack\'s height is greater than the current height, we have found the smallest height relatively to the previous height. Therefore, we pop off the stack and update its position in the array to contain the current index. The same process works when we go in reverse (from right to left).\n\nThen by the end, we just loop through all the heights and calculate the width, multiply it by the height, and update the largest area if it is greater than the answer so far.\n\n## Example\n\nLets use an example where `heights = [2,1,5,6,2,3]`\n\n**Compute from left to right**\n\n* i = 0\nStack = `[]` <-- TOP\nArray = `[-1,-1,-1,-1,-1,-1]`\n\nThere are no elements on the stack, so we just push the index `0`\n\n* i = 1\nStack = `[2]` <-- TOP\nArray = `[-1,-1,-1,-1,-1,-1]`\n\nSince the stack isn\'t empty, we compare `heights[elems.top()] = heights[0] = 2` against `heights[i] = heights[1] = 1`. Since the top element is greater than current element, we update it\'s array index to hold `i = 1` and pop `0` off the stack. The while condition is now false and at the end, we always push the current index onto the stack\n\n* i = 2\nStack = `[1]` <-- TOP\nArray = `[1,-1,-1,-1,-1,-1]`\n\nSince the stack isn\'t empty, we compare `heights[elems.top()] = heights[1] = 1` against `heights[i] = heights[2] = 5`. Since `1 < 5`, we just push the index `2`\n\n* i = 3\nStack = `[1,2]` <-- TOP\nArray = `[1,-1,-1,-1,-1,-1]`\n\nSince the stack isn\'t empty, we compare `heights[elems.top()] = heights[2] = 5` against `heights[i] = heights[3] = 6`. Since `5 < 6`, we just push the index `3`\n\n* i = 4\nStack = `[1,2,3]` <-- TOP\nArray = `[1,-1,-1,-1,-1,-1]`\n\nSince the stack isn\'t empty, we compare `heights[elems.top()] = heights[3] = 6` against `heights[i] = heights[4] = 2`. Since the top element is greater than current element, we update it\'s array index to hold `i = 4` and pop `3` off the stack. We check the while condition again\n\nSince the stack isn\'t empty, we compare `heights[elems.top()] = heights[2] = 5` against `heights[i] = heights[4] = 2`. Since the top element is greater than current element, we update it\'s array index to hold `i = 4` and pop `2` off the stack. We check the while condition again.\n\nSince the stack isn\'t empty, we compare `heights[elems.top()] = heights[1] = 1` against `heights[i] = heights[4] = 2`. Since `1 < 2`, we just push the index `4`\n\n* i = 5\nStack = `[1,4]` <-- TOP\nArray = `[1,-1,4,4,-1,-1]`\n\nSince the stack isn\'t empty, we compare `heights[elems.top()] = heights[4] = 2` against `heights[i] = heights[5] = 3`. Since `2 < 3`, we just push the index `5`\n\nThis generates the array `[1,-1,4,4,-1,-1]` which gives the index of the next smallest height\'s sindex of a particular height going from left to right\n\n*I am not doing it again for right to left, but it is the same idea*\n\n**Computing the largest area**\n\nHere are the two arrays:\n* Left to right = `[1,-1,4,4,-1,-1]`\n* Right to left = `[-1,-1,1,2,1,4]`\n\nNow we iterate and calculate the largest area for each\n\n* i = 0\nans = 0\n\nThe width is `left_to_right[i] - right_to_left[i] - 1 = left_to_right[0] - right_to_left[0] - 1 = 1 - (-1) - 1 = 1`. Therefore, the largest area is `1 * heights[i] = 1 * heights[0] = 1 * 2 = 2`. We update ans\n\n* i = 1\nans = 2\n\nThe width is `left_to_right[i] - right_to_left[i] - 1 = left_to_right[1] - right_to_left[1] - 1 = -1 - (-1) - 1 = -1`. Therefore, the largest area is `-1 * heights[i] = -1 * heights[1] = -1 * 1 = -1`. We do not update ans\n\n* i = 2\nans = 2\n\nThe width is `left_to_right[i] - right_to_left[i] - 1 = left_to_right[2] - right_to_left[2] - 1 = 4 - 1 - 1 = 2`. Therefore, the largest area is `2 * heights[i] = 2 * heights[2] = 2 * 5 = 10`. We update ans\n\n* i = 3\nans = 10\n\nThe width is `left_to_right[i] - right_to_left[i] - 1 = left_to_right[3] - right_to_left[3] - 1 = 4 - 2 - 1 = 1`. Therefore, the largest area is `1 * heights[i] = 1 * heights[3] = 1 * 6 = 6`. We do not update ans\n\n* i = 4\nans = 10\n\nThe width is `left_to_right[i] - right_to_left[i] - 1 = left_to_right[4] - right_to_left[4] - 1 = -1 - 1 - 1 = -3`. Therefore, the largest area is `-3 * heights[i] = -3 * heights[4] = -3 * 2 = -6`. We do not update ans\n\n* i = 5\nans = 10\n\nThe width is `left_to_right[i] - right_to_left[i] - 1 = left_to_right[5] - right_to_left[5] - 1 = -1 - 4 - 1 = -6`. Therefore, the largest area is `-6 * heights[i] = -6 * heights[5] = -6 * 3 = -18`. We do not update ans\n\n**PLEASE UPVOTE IF YOU FIND MY POST HELPFUL!! \uD83E\uDD7A\uD83D\uDE01**
['Array', 'Stack', 'Monotonic Stack', 'C++']