Space
Open
From Fieldwork
Scales
Archive
Imagine you are standing at index i looking left. You see a building of height H. You want to know: "How far to the right can this rectangle extend?"
If the next building is taller: That's great! The current rectangle of height H can continue through the taller building. We don't need to stop. We don't know the limit yet. So, we just push it onto the stack and wait.
If the next building is shorter: This is the "bad news." The rectangle of height H cannot pass through a shorter building. Its run is over.
This "drop" in height is the Right Boundary for the tall bar we just passed.
This is the only moment we have enough information to calculate the area for that tall bar, so we pop it and do the math.
Let's look at the specific moment we pop a bar.
The Bar we act on: Let's say we just popped a bar at index j. Its height is H.
The Right Boundary (i): We are currently at index i. We triggered the pop because heights[i] is shorter than H. So i is the first index to the right where the rectangle cannot exist. (Exclusive Right Bound)
The Left Boundary (stack[-1]): After popping j, the new top of the stack is stack[-1]. This index represents the first bar to the left that was shorter than H. (Exclusive Left Bound)
Why -1? We want the number of bars between stack[-1] and i.
Math: If you have boundaries L and R (exclusive), the count of items between them is R - L - 1.
class Solution:
def maximalRectangle(self, matrix: list[list[str]]) -> int:
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
heights = [0] * cols
max_area = 0
for r in range(rows):
for c in range(cols):
# Update the histogram heights
if matrix[r][c] == "1":
heights[c] += 1
else:
heights[c] = 0
# Calculate max area for this row's histogram
max_area = max(max_area, self.largestRectangleArea(heights))
return max_area
# Helper: Solves the 1D Histogram problem
def largestRectangleArea(self, heights: list[int]) -> int:
stack = [] # stores indices
max_a = 0
# Append a 0 height at the end to force pop remaining bars
# We perform a shallow copy + append to avoid modifying the original heights array repeatedly
current_heights = heights + [0]
for i, h in enumerate(current_heights):
start = i
# While the current bar is shorter than the bar at stack top,
# pop the stack and calculate area.
while stack and current_heights[stack[-1]] > h:
index = stack.pop()
height = current_heights[index]
# Width is current index - index of the previous item in stack - 1
width = i if not stack else i - stack[-1] - 1
max_a = max(max_a, height * width)
stack.append(i)
return max_aPractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode