Largest Rectangle in Histogram LeetCode Solution

Table of Contents

Problem Statement

Largest Rectangle in Histogram LeetCode Solution – 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.

Example

Test Case 1:

Input:

heights = [2, 1, 5, 6, 2, 3]

Output:

Explanation:

The above is a histogram where the width of each bar is 1. The largest rectangle is shown in the red area, which has an area of 10 units.

Approach:

Why could there be a better solution than O(n^2) ? How would we know that?

Because of the length of the array is n, the largest possible rectangle has to have a height of one of the elements of the array, that is to say, there are only n possible largest rectangles. So we don’t really need to go through every pair of bars, but should rather search by the height of the bar.

Why Stack?
At each step, we need the information of previously seen “candidate” bars – bars that give us hope. These are the bars of increasing heights. And since they’ll need to be put in the order of their occurrence, the stack should come to your mind.

Let’s take the example [2, 1, 5, 6, 2, 3]

Let’s start by adding a bar of height 0 as a starting point to the stack. This has no inherent meaning and is just done to make the solution more elegant

The first bar we see is the bar at the position 0 of height 2. It is definitely a “candidate bar” as it gives us hope of finding a larger rectangle, so we just add it to the stack.

The next one we see in the bar at the position 1 with height 1. At this point, we look at the stack and see that the “candidate bar” at the top of the stack is of height 2, and because of this 1, we definitely can’t do a rectangle of height 2 now, so the only natural thing to do at this point is to pop it out of the stack and see what area it could have given us.

This bar started at position -1 (which is now at the top of the stack), and ended at position 1, thus giving a width of 1−(−1)−1=1, and a height of 2 hence we update our maxArea to 2, and now check the next element on top of the stack (to see if that could be popped out as well) – and since it is 0 < 1, it can’t be popped out. Thus,

height = stack.pop()

width = i – stack[-1] – 1

maxArea = max(maxArea, width*height)

We now append 1 to the stack and move onto position 2 with the bar of height 5. We don’t need to pop out any elements from the stack, because the bar with height 5 can form a rectangle of height 1 (which is on top of the stack), but the bar with height 1 cannot form a rectangle of height 5 – thus it is still a good candidate (in case 5 gets popped out later). We append 5 to the stack and move forward without any eliminations.

We observe the same thing when we arrive at 6 (at position 3).

At this point, it should be clear that we only pop from the stack when the height of the current bar is lower than the height of the bar at the top of the stack.

When we reach the bar at position 4, we realize we can’t do a bar of height 6 anymore, so let’s see what it can give us and pop it out. The height of this rectangle is 6, and the width is $i - s t a c k [- 1] - 1 = 4 - 2 - 1 = 1$ .

We now look at the top of the stack and see another rectangle forming.

It is important to notice here how the elimination of 6 from stack has no effect on it being used to form the rectangle of height 5

We now have our $m a x A r e a = 10$ and we have three elements in the stack, and we move onto a position 5 with the bar of height 3. Since 3 > 2, we append it to the stack.

We now move on to the next element which is the position 6 (or -1) with height 0 – our dummy element which also ensures that everything gets popped out of the stack! We check all possible rectangles while we pop out elements from the stack. Element with $(h e i g h t, w i d t h)$ being $(3, 1)$ , $(2, 2)$ , $(1, 5)$ , none of which have area larger than $10$ .

Code for Largest Rectangle in Histogram LeetCode Solution

Python Program

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        stack = [-1]
        heights.append(0)
        ans = 0
        for i, height in enumerate(heights):
            while heights[stack[-1]] > height:
                h = heights[stack.pop()] 
                w = i - stack[-1] - 1
                ans = max(ans, h*w)
            stack.append(i)
        heights.pop()
        return ans

Java Program

class Solution {
    public int largestRectangleArea(int[] h) {
        int n = h.length, i = 0, max = 0;
    
        Stack<Integer> s = new Stack<>();

        while (i < n) {
          // as long as the current bar is shorter than the last one in the stack
          // we keep popping out the stack and calculate the area based on
          // the popped bar
          while (!s.isEmpty() && h[i] < h[s.peek()]) {
            // tricky part is how to handle the index of the left bound
            max = Math.max(max, h[s.pop()] * (i - (s.isEmpty() ? 0 : s.peek() + 1)));
          }
          // put current bar's index to the stack
          s.push(i++);
        }

        // finally pop out any bar left in the stack and calculate the area based on it
        while (!s.isEmpty()) {
          max = Math.max(max, h[s.pop()] * (n - (s.isEmpty() ? 0 : s.peek() + 1)));
        }

        return max;
    }
}

Complexity Analysis for Largest Rectangle in Histogram LeetCode Solution

Time Complexity: O( numbers are pushed and popped.

Space Complexity: . Stack is used.