L13. Maximal Rectangle | Stack and Queue Playlist

1. Problem Statement and Objective

The Maximal Rectangle problem requires us to find the maximum possible area containing exclusively ones (1) within a given $N \times M$ 2D binary matrix.

Matrix Example:
[1, 0, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 0, 0, 1, 0]

Possible Valid Rectangles:
- Area 5: [1, 1, 1, 1, 1] (single row, width 5, height 1)
- Area 6: [1, 1, 1] stacked across rows (width 3, height 2)

Note: Any candidate rectangle that incorporates even a single zero (0) is invalid. The goal is to return the absolute maximum valid area.

2. Prerequisite and Mental Connection

Solving this problem efficiently relies directly on a known predecessor problem: Largest Rectangle in Histogram.

Instead of treating the 2D matrix as an isolated geometric puzzle, we can reduce each row of the matrix into a histogram problem. By calculating the consecutive vertical heights of ones column-wise from top to bottom at each row, every individual row of our 2D matrix can transform into a 1D histogram array. We then pass this 1D array directly into our largestRectangleArea function.

3. Visualizing the Row-by-Row Histogram Reduction

Let us walk through how horizontal slices across the matrix generate equivalent 1D histograms.

• Stopping at Row 0:

  CODE

  Copy

  Array: [1, 0, 1, 0, 0]
  Bars:   1  -  1  -  -
  Max Area: 1
  

• Stopping at Row 1:

  CODE

  Copy

  Array: [2, 0, 2, 1, 2]
  Bars:   2  -  2  1  2
  Max Area: 3 (from subarray [2, 1, 2] or similar configurations)
  

• Stopping at Row 2 (The Maximal Area):

  Structure & Concept Flow

  Copy DiagramCopy

  Array: [3, 1, 3, 2, 3]

  Bars: 3 1 3 2 3

  Max Area: 6 (width 3, height 2 -> sub-rectangle of all ones)

   

• Stopping at Row 3:

  CODE

  Copy

  Array: [4, 0, 0, 3, 0]
  Bars:   4  -  -  3  -
  Max Area: 4
  

4. Optimizing Height Computation via Prefix Sum (Vertical Accumulation)

If we re-scanned and recounted vertical ones from scratch for every single row, our time complexity would balloon unnecessarily. Instead, we use a specialized variant of prefix sums computed column-wise from top to bottom.

The Accumulation Rule:

• If matrix[i][j] == 1, add the value from the row directly above: sum = sum + matrix[i][j].
• If matrix[i][j] == 0, immediately reset the running column sum to 0 (because a histogram bar is broken by a zero gap).

5. Complete Algorithm Workflow

1. Initialize Dimensions: Extract row count $N$ and column count $M$ from the input matrix.
2. Setup Storage: Create a 2D prefix sum array (prefixSum) of dimensions $N \times M$ initialized to zeros, and a variable maxArea = 0.
3. Build Column Heights: Iterate column by column ($j$ from $0$ to $M-1$), maintaining a running vertical sum. Reset sum to 0 upon encountering a zero; otherwise, accumulate and store in prefixSum[i][j].
4. Evaluate Histograms: Iterate through each row index $i$ from $0$ to $N-1$:
   • Pass the entire 1D row prefixSum[i] into the helper function largestRectangleArea(row).
   • Update maxArea = max(maxArea, largestRectangleArea(prefixSum[i])).
5. Return Result: Output maxArea.

6. Pseudocode Implementation

Below is the clean pseudocode demonstrating the complete approach:

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    n = len(matrix)
    m = len(matrix[0])
    max_area = 0
    
    # Step 1: Create 2D prefix sum array for bar heights
    prefix_sum = [[0] * m for _ in range(n)]
    
    # Step 2: Populate prefix_sum column-wise
    for j in range(m):
        current_sum = 0
        for i in range(n):
            if matrix[i][j] == 0:
                current_sum = 0
            else:
                current_sum += matrix[i][j]
            prefix_sum[i][j] = current_sum
            
    # Step 3: Evaluate largest histogram for each row
    for i in range(n):
        current_row_max = largestRectangleArea(prefix_sum[i])
        max_area = max(max_area, current_row_max)
        
    return max_area

def largestRectangleArea(heights):
    # Standard monotonic stack implementation from L12
    stack = []
    max_area = 0
    n = len(heights)
    
    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
            max_area = max(max_area, height * width)
        stack.append(i)
        
    return max_area

7. Complexity Analysis

8. Summary and Key Takeaways

• Problem Reduction: Complex 2D matrix problems can often be broken down and solved using simpler 1D data structures like histograms.
• Prefix Sum Accumulation: Vertical tracking of consecutive ones allows us to construct histogram bars dynamically row-by-row in linear time.
• Zero Interruptions: Whenever a matrix cell contains 0, the vertical bar height must immediately reset to 0 because rectangle continuity is broken.
• Monotonic Stack Synergy: Reusing the largestRectangleArea algorithm (from Lecture 12) directly unlocks efficient area calculation for each converted row.
• Input Preservation: Allocating a separate prefixSum matrix rather than mutating the original input matrix is an industry-best practice for clean, side-effect-free code.
• Optimal Efficiency: The combined approach achieves an optimal time complexity of $O(N \times M)$, avoiding exhaustive brute-force rectangle enumeration.