84. Largest Rectangle in Histogram — LeetCode(Python)

I got you!

Problem:

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 1:

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.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

• 1 <= heights.length <= 105
• 0 <= heights[i] <= 104

Solution:

1. Two-Pass Stack Solution —

maxArea = 0
stack = [] # pair: (index, height)
        
for i, h in enumerate(heights):
    start = i
    while stack and stack[-1][1] > h:
        index, height = stack.pop()
        maxArea = max(maxArea, height * (i - index))
        start = index
    stack.append((start, h))
        
for i, h in stack:
    maxArea = max(maxArea, h * (len(heights) - i))
return maxArea

Explanation —

We use a stack to solve this problem.

We traverse the list of heights and append each height to our stack.

When we come across a height that is smaller than the latest added height,

• we keep popping from the stack until this is not the case.
• we calculate the area a given bar would form.
• we keep updating the max_area.

After finishing one iteration of our list of heights, we might still be left with some bars in our histogram that did not pop out because we did not have a shorter bar ahead of them.

This means that these bars will be allowed to create rectangles that go to the end of the list.

Therefore, we traverse the stack now, and update the max_area variable as we go. The area these left out bars create is equal to their height multiplied by the distance they are away from the end of our list.

Finally, we return the max_area.

Time and Space Complexity —

Since we are iterating over the list heights only once and then the stack once, we can say that our algorithm runs in linear time.

Also, we require linear amount of extra space to store the bars in our stack.

Thus, if n is the length of the list heights,

Time Complexity: O(n)

Space Complexity: O(n)

2. Single-Pass Stack Solution —

heights.append(0)
maxArea = 0
stack = [] # pair: (index, height)
        
for i, h in enumerate(heights):
    start = i
    while stack and stack[-1][1] > h:
        index, height = stack.pop()
        maxArea = max(maxArea, height * (i - index))
        start = index
    stack.append((start, h))
        
for i, h in stack:
    maxArea = max(maxArea, h * (len(heights) - i))
return maxArea

Explanation —

In the previous solution, we can solve the problem of having to traverse the leftover elements in the stack again by simply appending a ‘0’ at the end of our list of heights.

This would mean that our list is always guaranteed to have a bar at the end that is smaller than all other bars and therefore every element in the stack will be popped out.

Genius, am I right lol?

Time and Space Complexity —

Since only an constant time and constant space operation has been added to the code in Solution 1, our time and space complexities remain the same.

Thus, if n is the length of the list heights,

Time Complexity: O(n)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏