Maximum Rectangle Area with All 1's | DP on Rectangles

Finding the maximum rectangular submatrix containing exclusively 1s within an $N \times M$ binary matrix is a classic advanced algorithmic challenge. By leveraging dynamic programming concepts—specifically accumulating historical state—we can reduce this 2D matrix scanning problem into a series of 1D Largest Rectangle in Histogram sub-problems.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given an $N \times M$ binary matrix filled with 0s and 1s, our goal is to find the maximum possible rectangle composed entirely of 1s and return its area (Length $\times$ Breadth).

The Challenge of Naive Exploration

• Brute Force Inefficiency: Checking every possible top-left and bottom-right coordinate pair results in an exorbitant time complexity (typically cubic or quartic relative to matrix dimensions), which fails immediately for large matrices.
• Interconnected Constraints: A rectangle of 1s cannot contain any 0s. A single 0 anywhere inside a candidate region invalidates the entire rectangle.
• The Need for Optimal Reduction: Rather than inspecting every 2D sub-grid independently, we need a systematic way to compress rows into rolling 1D profiles.

2. Core Mental Model: Building Profiles Row by Row

The foundational intuition behind this solution is viewing each row of the matrix as a baseline for a vertical city skyline (histogram), where the height of each building corresponds to the consecutive count of 1s directly above it (including the current row).

Real-Life Analogy: Measuring Water Levels or Building Heights

Imagine walking down a street row by row from top to bottom. If you look straight down at the ground from any point, the number of stacked blocks directly above you (unbroken by empty gaps of 0) represents the height of a building.

• If you encounter a 1, the building grows taller by $1$ unit.
• If you encounter a 0, the building collapses entirely, resetting its height to $0$.

3. The Prerequisite: Largest Rectangle in Histogram

Before solving the 2D matrix problem, we rely on a well-known sub-problem: Finding the Largest Rectangle in a Histogram.

• Given an array of histogram bar heights (e.g., [2, 1, 5, 6, 2, 3]), we need to find the contiguous sub-array of bars that can form the largest internal rectangle.
• Using an optimal monotonic stack approach, we can solve the 1D histogram problem in linear time $\mathcal{O}(M)$ where $M$ is the number of bars (columns).
• We assume access to a helper function, say largestRectangleArea(vector<int>& heights), which takes a histogram vector and returns the maximum rectangular area possible within it.

4. Step-by-Step Evolution: Transitioning from 2D Matrix to 1D Histograms

As we iterate downward through each row of the $N \times M$ matrix, we maintain a running heights vector of size $M$.

The State Transition Rule

For every cell at coordinate (i, j):

1. If matrix[i][j] == 1: Increment our running height profile: heights[j] += 1.
2. If matrix[i][j] == 0: Reset our running height profile: heights[j] = 0.

Let's trace this evolution across a sample $4 \times 5$ matrix:

5. Complete Flow Walkthrough

Below is the complete execution pipeline showing how data flows from the 2D matrix traversal down to the monotonic stack histogram solver:

6. Complete C++ Production Implementation

Here is the clean, decoupled C++ implementation integrating the histogram helper function with the row-by-row accumulation logic:

class Solution {
private:
    // Helper function to find the largest rectangle in a histogram using a monotonic stack
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st;
        int maxArea = 0;
        
        for (int i = 0; i <= n; i++) {
            while (!st.empty() && (i == n || heights[st.top()] >= heights[i])) {
                int height = heights[st.top()];
                st.pop();
                int width;
                if (st.empty()) {
                    width = i;
                } else {
                    width = i - st.top() - 1;
                }
                maxArea = max(maxArea, width * height);
            }
            st.push(i);
        }
        return maxArea;
    }

public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        
        int n = matrix.size();
        int m = matrix[0].size();
        
        vector<int> heights(m, 0);
        int maxArea = 0;
        
        // Iterate through each row and build the histogram profile
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // Assuming matrix contains character '1' and '0'
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            // Compute max rectangular area for the current row's histogram
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        
        return maxArea;
    }
};

7. Complexity Analysis & Why It Is Considered DP

Time & Space Complexity Breakdown

Why is this Dynamic Programming?

This problem fits cleanly into the Dynamic Programming paradigm because we memorize and build upon past states. Rather than recalculating building heights from scratch for every single row, we reuse the accumulated heights from the previous row (heights[j] += 1), carrying forward historical sub-problem results to make the current row's computation trivial.

8. Summary and Key Takeaways

• Problem Reduction: The 2D Maximum Rectangle problem can be successfully transformed into $N$ separate 1D Largest Rectangle in Histogram problems.
• State Accumulation: As we traverse downward row by row, we increment building heights when encountering 1s and reset them to 0 when encountering 0s.
• Monotonic Stack Efficiency: Using a monotonic stack for the histogram sub-problem keeps the per-row evaluation time linear ($\mathcal{O}(M)$).
• Overall Optimal Efficiency: The combined algorithm achieves an optimal time complexity of $\mathcal{O}(N \times M)$ with an auxiliary space complexity of $\mathcal{O}(M)$.
• Dynamic Programming Connection: Reusing historical row heights to compute current row profiles exemplifies memoization and optimal substructure.