Largest Rectangle in Historgram

Tags: monotonic stack, stack

Problem Statement:

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:

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.

Intuition:

for any index (say i), the max area that can be formed including that element is
area = heights[i] * (nse[i] - pse[i] -1).

Note: For one pass solution, the key insight (memorize this)
NSE is discovered when an element is popped
PSE is discovered when an element is pushed
That’s the entire “one-pass” trick.

Code:

My Solution

def largestRectangleArea(self, heights: List[int]) -> int:
	n = len(heights)
	nse = [n] * n
	stk = []
	for i,h in enumerate(reversed(heights)):
		i = n - i - 1
		while stk and heights[stk[-1]] >= h:
			stk.pop()
		if stk:
			nse[i] = stk[-1]
		stk.append(i)

	pse = [-1] * n
	stk = []
	for i,h in enumerate(heights):
		while stk and heights[stk[-1]] >= h:
			stk.pop()
		if stk:
			pse[i] = stk[-1]
		stk.append(i)

	mx = 0
	for i, h in enumerate(heights):
		area = h * (nse[i] - pse[i] - 1)
		mx = max(mx, area)

	return mx
        

One Pass Solution

def largestRectangleArea(self, heights: List[int]) -> int:
	n = len(heights)
	stk = []
	left = [-1] * n
	right = [n] * n
	for i, h in enumerate(heights):
		while stk and heights[stk[-1]] >= h:
			right[stk[-1]] = i
			stk.pop()
		if stk:
			left[i] = stk[-1]
		stk.append(i)
	return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))