Maximal Rectangle

1. Build a Histogram Row by Row

• Maintain a heights array of length cols, initialized to all zeros
• For each row in the matrix, update each column's height: if matrix[r][c] is '1', increment heights[c] by 1; otherwise reset it to 0
• This transforms the 2D problem into a series of "largest rectangle in histogram" problems

2. Apply Largest Rectangle in Histogram

• After updating heights for each row, compute the largest rectangle area in the current histogram
• Use a monotonic stack to efficiently find the largest rectangle

3. Monotonic Stack Approach

• Iterate through the histogram bars from left to right
• Maintain a stack of indices in increasing order of bar heights
• When the current bar is shorter than the bar at the top of the stack, pop from the stack
• For each popped bar, calculate the rectangle area using that bar's height and the width determined by the current index and the new stack top

4. Calculate Width for Each Popped Bar

• When popping index j at current index i, the width extends from the element after the new stack top to i - 1
• If the stack is empty after popping, the width is i (the bar extends all the way to the left)
• Otherwise, the width is i - stack[top] - 1

5. Handle Remaining Bars

• After processing all bars, append a virtual bar of height 0 to flush all remaining bars from the stack
• This ensures every bar is processed and its maximum rectangle is considered

6. Track the Global Maximum

• After each row's histogram is processed, update the global maxArea with the largest rectangle found
• Return maxArea after all rows are processed

Key Insight

By building histograms row by row, we reduce the 2D maximal rectangle problem to repeated 1D largest-rectangle-in-histogram problems. The monotonic stack solves each histogram in O(cols) time, giving an overall time complexity of O(rows × cols). Space complexity is O(cols) for the heights array and the stack.