Framework Thinking - Neetcode 150 - Largest Rectangle In Histogram
Here is solution for Largest Rectangle In Histogram.
1. Understand the problem
-
You’re given an array heights[] where each element represents the height of a bar in a histogram. Each bar has width = 1.
-
Your task is to find the area of the largest rectangle that can be formed among the bars.
-
Example:
Input: [2,1,5,6,2,3]
Output: 10 (Using bars with heights 5 and 6: area = 5 → 2 bars → 5*2 = 10)
2. Clarify contraints
- Can heights array be empty?
- If yes, return 0.
- Can histogram contain zero height bars?
- Yes, e.g., [0,2,0].
- Max size of heights?
- Usually up to 10⁵ → must optimize.
- Max height value?
- Usually ≤ 10⁹, but doesn’t affect complexity.
- Should solution run in O(n) or is O(n²) acceptable?
- Optimal expected is O(n).
3. Dry run examples
- Example 1:
| |
| | |
|___|___|
1 1 1 ← height = 1
=> Height = 3
- Example 2:
[7, 1, 7, 2, 2, 4]
Note: Area = curr_val + expand(left) + expand(right)
4. Brainstorm solutions
4.1. Brute force - O(N^2)
-
For each bar, expand left and right until hitting a bar smaller than current height.
-
Caculate area = curr_val + expand(left) + expand(right)
-
Time: O(N^2)
-
Space: O(N)
4.2. Segment Tree Approach - O(NlogN).
-
Idea: minIdx = st.query(l, r) return index of the minimum height inside the range [l, r]
-
The largest rectangle either:
-
uses the minimum height in the full range [L, R],
-
or lies entirely in the left [L, m-1] part,
-
or entirely in the right [m+1, R].
-
-
Time: O(NlogN).
-
Space: O(N).
4.3. Two Stack - O(N).
- Use stack to store indices of increasing bars. When encountering a smaller bar, pop from stack and calculate area using popped height as smallest.
=> Left stack and right stack to find the nearest smaller array.
-
Time: O(N).
-
Space: O(N).
4.4. Stack (One Pass)
🧠 Core Idea (Both Solutions Use This)
For each bar:
✔ The rectangle extends left until a smaller bar ✔ Extends right until a smaller bar ✔ Area = height × width
- Each bar remembers how far left it extends using start.
while stack and stack[-1][1] > h:
index, height = stack.pop()
maxArea = max(maxArea, height * (i - index))
start = index
stack.append((start, h))
b
/\ d
/ \ /
/ \ /
a c
- Monotonic stack always keep order [a, b] => So we only find c that c < b, and calculate [right - left - i] * height.
4.5. Stack (Optimal)
- Same idea of stack one pass.
5. Implement solutions
5.1. Brute Force - O(N^2)
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
maxArea = 0
for i in range(n):
height = heights[i]
rightMost = i + 1
while rightMost < n and heights[rightMost] >= height:
rightMost += 1
leftMost = i
while leftMost >= 0 and heights[leftMost] >= height:
leftMost -= 1
rightMost -= 1
leftMost += 1
maxArea = max(maxArea, height * (rightMost - leftMost + 1))
return maxArea
-
Time: O(N^2).
-
Space: O(1).
5.2. Divide And Conquer (Segment Tree) - O(NlogN)
-
Idea: find something in subarray with O(logN).
-
Build the tree O(N).
class MinIdx_Segtree:
def __init__(self, N, A):
self.n = N
self.INF = int(1e9)
self.A = A
while (self.n & (self.n - 1)) != 0:
self.A.append(self.INF)
self.n += 1
self.tree = [0] * (2 * self.n)
self.build()
def build(self):
for i in range(self.n):
self.tree[self.n + i] = i
for j in range(self.n - 1, 0, -1):
a = self.tree[j << 1]
b = self.tree[(j << 1) + 1]
if self.A[a] <= self.A[b]:
self.tree[j] = a
else:
self.tree[j] = b
def update(self, i, val):
self.A[i] = val
j = (self.n + i) >> 1
while j >= 1:
a = self.tree[j << 1]
b = self.tree[(j << 1) + 1]
if self.A[a] <= self.A[b]:
self.tree[j] = a
else:
self.tree[j] = b
j >>= 1
def query(self, ql, qh):
return self._query(1, 0, self.n - 1, ql, qh)
def _query(self, node, l, h, ql, qh):
if ql > h or qh < l:
return self.INF
if l >= ql and h <= qh:
return self.tree[node]
a = self._query(node << 1, l, (l + h) >> 1, ql, qh)
b = self._query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh)
if a == self.INF:
return b
if b == self.INF:
return a
return a if self.A[a] <= self.A[b] else b
class Solution:
def getMaxArea(self, heights, l, r, st):
if l > r:
return 0
if l == r:
return heights[l]
minIdx = st.query(l, r)
return max(max(self.getMaxArea(heights, l, minIdx - 1, st),
self.getMaxArea(heights, minIdx + 1, r, st)),
(r - l + 1) * heights[minIdx])
def largestRectangleArea(self, heights):
n = len(heights)
st = MinIdx_Segtree(n, heights)
return self.getMaxArea(heights, 0, n - 1, st)
-
Time: O(NlogN).
-
Space: O(N).
5.3. Two Stack - O(N).
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
stack = []
leftMost = [-1] * n
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
leftMost[i] = stack[-1]
stack.append(i)
stack = []
rightMost = [n] * n
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
rightMost[i] = stack[-1]
stack.append(i)
maxArea = 0
for i in range(n):
leftMost[i] += 1
rightMost[i] -= 1
maxArea = max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1))
return maxArea
-
Time: O(N).
-
Space: O(N).
5.4. Monotonic Stack - O(N), keep left < a, find right < a
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
maxArea = 0
stack = []
for i in range(n + 1):
while stack and (i == n or heights[stack[-1]] >= heights[i]):
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
maxArea = max(maxArea, height * width)
stack.append(i)
return maxArea
-
Time: O(N).
-
Space: O(N).