84.Largest_Rectangle_in_Histogram(Hard).md

84. Largest Rectangle in Histogram (Hard)

Date and Time: Oct 17, 2024, 16:52 (EST)

Link: https://leetcode.com/problems/largest-rectangle-in-histogram/

Question:

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 <= 10^5

• 0 <= heights[i] <= 10^4

Walk-through:

Use stack[] to save [index, height] until the current height is less than previous height in stack stack[-1][1]. Then we need to calculate the area of previous height by height * (i - index), and append new height into stack [index, height], because previous index can contribute to this height. (i is current height's index, index is the previous height's index we pop from stack)

Lastly, we may encounter heights are increasing or the last parts are increasing. We just calculate the area by height * (len(heights) - i), because they are all increasing, means heigh come after this current height are all greater or equal to this height, and there are len(heights) - i of them.

Python Solution:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # Save all numbers and its index into stack
        # Until current height < stack[-1][1]
        # Calculate that area with i - index (from stack)
        # Update start = index
        # Append((start, h)), because the prev index we pop from stack can be extended with this current height h

        # TC: O(n), SC: O(n)
        stack = []
        area = 0
        for i, height in enumerate(heights):
            start = i
            while stack and stack[-1][1] > height:
                index, prevHeight = stack.pop()
                area = max(area, prevHeight * (i - index))
                start = index
            stack.append([start, height])
        
        # Case when heights are increasing or the last parts of heights are increasing
        for i, height in stack:
            area = max(area, (len(heights) - i) * height)
        return area

Time Complexity: $O(n)$, we only loop over heights, and pop() from stack[] only takes $O(1)$.
Space Complexity: $O(n)$