Stack - Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Constraints:

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

Solution 1 - Using a Stack

When finding area of largest rectangle based on heights in the heights array, there could be 2 different scenarios

If a smaller height comes after bigger height: For example if the heights are [2,1,3] In this case, area that can be drawn from the first height 2, will be reduced to height 1 if it need to be included with next height which is 1.
If a bigger height comes after smaller height: For example if the heights are [2,3] In this case, area that can be drawn to the second height 3, we can include the smaller heights prior to that as well.

In this approach, we are going to use a Stack and store index, height pair in a monitonically increasing order, and compute area if we see a smaller height than previous and store that in a variable maxArea, and at the end go through the stack elements and compute area possible from each element until the end, we can get the total width possible using the index of that height. One thing that we do differently when storing the index is that, if there is a smaller height after a bigger height, since we are building monotonically increasing stack, we will pop the bigger height elements before adding the current one, but we store index as the last element that was popped, the reason we do that is because say if the input array is [2,1,3,1], before adding height 1 to the stack, we will pop height 2, and when storing 1 we will store it win index 1 since we can still take 1 unit height from the element height 2.

Let's look at an example, heights = [2, 1, 3, 1] Example with explanation

First, we will add 1^st height 1 to the stack, stack = [(0, 2)] and maxArea = 0.
Next, 2^nd height is 1, which is smaller than the previous height, so we pop the previous element from stack and update maxArea = (height * width) = 2 * 1 = 2 and stack becomes stack = [(0, 1)], index will still be 0 because we can still use 1 unit of height from the previous height 2, when we have to compute area at a later height, this will help to get the width (from which index, we can consider the height).
Next, 3^rd element is 3, since this is bigger height than the previous height in stack, we will add it to stack stack = [(0, 1), (2, 3)] and maxArea = 2
Next, 4^th height is 1, which is smaller than the previous height, so we pop the previous element from stack and update maxArea = (height * width (current index - previous element index)) = 3 * (3-2) = 3 and stack becomes stack = [(0, 1), [2, 1]], index will be 2 because we can still use 1 unit of height from the previous height 3.
Now, let's look at the elements in stack and compute the area possible at those indexes, by taking the height from the stack and for the width take heights.length - index this will give how many unit heights can be considered with that height.
- Area for the first element will be = 1 (height) * 4 = 4 ( heights array length - index = 4 - 0, that is 1 unit height can be considered from all heights).
- Area for the second element will be = 1 (height) * 3 = 3
So the max area will be 4.

import java.util.Stack; public class LargestRectangleInHistogram { static int largestRectangleArea(int[] heights) { int maxArea = 0; Stack<int[]> indexToHeight = new Stack<>(); // monotonically increasing order for(int i=0; i<heights.length; i++) { int startIndex = i; int height = heights[i]; while(!indexToHeight.isEmpty() && indexToHeight.peek()[1] > height) { // if top of the stack height is greater than current one, then we cannot extend previous height int[] indexHeight = indexToHeight.pop(); int indexE = indexHeight[0]; int heightE = indexHeight[1]; maxArea = Math.max(maxArea , ((i - indexE) * heightE)); startIndex = indexE; } indexToHeight.push(new int[]{startIndex, height}); } // in the above loop, it may not have computed maxArea if the array is in increasing order for(int[] indexHeight : indexToHeight) { maxArea = Math.max(maxArea, indexHeight[1] * (heights.length - indexHeight[0])); } return maxArea; } public static void main(String[] args) { System.out.println(largestRectangleArea(new int[]{2,1,5,6,2,3})); System.out.println(largestRectangleArea(new int[]{2,4})); } }

Complexity Analysis:

Time complexity: Time complexity for the solution will be O(n) where n is the length of input array heights.
Space complexity: O(n) for storing elements into stack.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: