Maximum Size Rectangle Binary Sub Matrix With All 1s Leetcode

This article will guide you through solving the "Maximal Rectangle" problem, which involves finding the largest rectangle containing only '1's in a binary matrix. You will learn about efficient approaches, including dynamic programming and the "Largest Rectangle in Histogram" technique.

Problem Statement

Given a rows x cols binary matrix filled with '0's and '1's, the task is to find the largest rectangle containing only '1's and return its area. This problem often appears in contexts requiring the analysis of contiguous regions in grid-based data structures.

Consider a practical scenario like analyzing an image represented as a binary matrix where '1's are features of interest and '0's are background. Identifying the largest rectangular area of '1's could correspond to finding the largest contiguous feature.

Example

Let's consider a sample binary matrix:

[[1, 0, 1, 0, 0],
 [1, 0, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [1, 0, 0, 1, 0]]

For this matrix, the maximal rectangle of '1's has an area of 6. This rectangle is formed by the submatrix from row 1, column 2 to row 2, column 4 (using 0-based indexing), which is:

[1, 1, 1]
[1, 1, 1]

Background & Knowledge Prerequisites

To effectively understand the solutions, it is helpful to have a grasp of:

• Arrays and Matrices: Basic operations on 2D arrays.
• Dynamic Programming (DP): Understanding how to build up solutions from subproblems.
• Stack Data Structure: Its operations (push, pop, peek) and common applications.
• Largest Rectangle in Histogram Problem: This is a crucial subproblem. Given an array of non-negative integers representing histogram bar heights, find the area of the largest rectangle in the histogram.

Use Cases or Case Studies

This problem and its underlying techniques are applicable in various domains:

• Image Processing: Identifying the largest contiguous region of a specific pixel value (e.g., detecting large objects or uniform areas).
• Game Development: Collision detection in 2D grid-based games, finding the largest clear area for character movement or object placement.
• Data Analysis: Finding dense clusters or regions of interest in tabular binary data.
• Circuit Design: Optimizing layout by finding the largest rectangular space available for component placement.
• Bioinformatics: Analyzing patterns in genomic sequences represented as binary matrices.

Solution Approaches

There are several ways to tackle the Maximal Rectangle problem. We will focus on the most efficient one, which leverages dynamic programming and the Largest Rectangle in Histogram (LRH) problem.

1. Brute Force (Conceptual Overview)

One-line summary: Iterate through all possible top-left and bottom-right corners, then check if the submatrix formed contains only '1's.

Explanation: A straightforward but inefficient approach is to consider every possible subrectangle within the matrix. For each potential subrectangle, you would then iterate through all its cells to verify if they are all '1's.

• Complexity: If the matrix is m x n, there are O((m*n)^2) possible subrectangles. Checking each subrectangle takes O(m*n) time. This leads to an overall time complexity of O((m*n)^3), which is too slow for larger matrices.

2. Dynamic Programming with Largest Rectangle in Histogram

One-line summary: Convert each row of the binary matrix into a histogram, where bar heights represent consecutive '1's upwards, and then apply a stack-based algorithm to find the largest rectangle in each generated histogram.

This approach transforms a 2D problem into a series of 1D problems.

Stepwise Explanation

1. Initialize Heights Array: Create an array, say heights, of size cols. This array will store the current histogram's bar heights. Initialize all its elements to 0.

1. Iterate Through Rows: Process the matrix row by row. For each row i:
   • Update heights Array: For each column j in the current row i:

If matrix[i][j] is '1', increment heights[j] by 1. This means the '1' extends the current column's consecutive block of '1's upwards.

If matrix[i][j] is '0', reset heights[j] to 0. This breaks any continuous block of '1's from above.

Solve Largest Rectangle in Histogram: After updating the heights array for the current row, treat heights as a histogram. Calculate the largest rectangle area that can be formed within this histogram.

Update Maximum Area: Keep track of the maximum area found across all rows.

The largestRectangleArea Subproblem (Stack-Based)

This is a critical component for efficiency. Given a heights array, we can find the largest rectangle in O(N) time using a stack.

• Algorithm:

1. Initialize an empty stack (to store indices of bars).
2. Initialize max_area to 0.
3. Iterate through the heights array (and effectively an imaginary bar of height 0 at the end to process remaining stack elements).
4. While the stack is not empty AND the current bar's height is less than or equal to the height of the bar at the stack's top:
   • Pop an index h from the stack.

Calculate the width: If the stack is empty, the width is the current index i. Otherwise, the width is i - stack.top() - 1.

Calculate the area: heights[h] * width.

Update max_area if the calculated area is larger.

1. Push the current index i onto the stack.
2. After iterating through all bars, process any remaining bars in the stack using the same logic, but the i (current index) would be the array length N.

This stack-based method ensures that each bar is pushed and popped from the stack at most once, leading to an O(N) time complexity for the LRH problem.

Code Example (C)

Since the problem context implies C, we will implement a basic stack using an array.

// Maximal Rectangle
#include <stdio.h>
#include <stdlib.h> // For malloc, free
#include <string.h> // For memset
#include <math.h>   // For fmax (though standard max is fine)

// Helper function to find the maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Function to find the largest rectangle area in a histogram
// Uses an array-based stack for simplicity in C
int largestRectangleArea(int* heights, int num_cols) {
    // We'll use a stack to store indices of bars
    // MAX_COLS needs to be large enough, or use dynamic allocation for stack
    // For LeetCode-like problems, num_cols typically up to 200, so a static
    // array stack of that size is acceptable.
    int* stack = (int*) malloc(sizeof(int) * (num_cols + 1)); // +1 for sentinel
    if (stack == NULL) {
        perror("Failed to allocate stack");
        return 0;
    }
    int top = -1; // Stack is empty

    int max_area = 0;
    int i = 0;

    while (i < num_cols) {
        // If current bar is taller than or equal to stack top, push it
        if (top == -1 || heights[stack[top]] <= heights[i]) {
            stack[++top] = i++;
        } else {
            // If current bar is smaller, pop from stack and calculate area
            int h_idx = stack[top--];
            int height = heights[h_idx];
            int width = (top == -1) ? i : (i - stack[top] - 1);
            max_area = max(max_area, height * width);
        }
    }

    // Process remaining elements in stack
    while (top != -1) {
        int h_idx = stack[top--];
        int height = heights[h_idx];
        int width = (top == -1) ? i : (i - stack[top] - 1);
        max_area = max(max_area, height * width);
    }

    free(stack);
    return max_area;
}

// Main function to solve Maximal Rectangle
int maximalRectangle(char** matrix, int matrix_rows, int matrix_cols) {
    if (matrix_rows == 0 || matrix_cols == 0) {
        return 0;
    }

    // Heights array for the histogram, needs to be dynamically allocated
    int* heights = (int*) malloc(sizeof(int) * matrix_cols);
    if (heights == NULL) {
        perror("Failed to allocate heights array");
        return 0;
    }
    // Initialize heights to 0
    memset(heights, 0, sizeof(int) * matrix_cols);

    int max_overall_area = 0;

    // Iterate through each row
    for (int i = 0; i < matrix_rows; i++) {
        // Update heights for the current row
        for (int j = 0; j < matrix_cols; j++) {
            if (matrix[i][j] == '1') {
                heights[j]++;
            } else {
                heights[j] = 0; // Reset height if '0' is encountered
            }
        }

        // Calculate largest rectangle in the current histogram
        max_overall_area = max(max_overall_area, largestRectangleArea(heights, matrix_cols));
    }

    free(heights);
    return max_overall_area;
}

// Example usage
int main() {
    // Example 1
    char* matrix1[] = {
        "10100",
        "10111",
        "11111",
        "10010"
    };
    int rows1 = 4;
    int cols1 = 5;
    printf("Matrix 1:\\n");
    for (int i = 0; i < rows1; i++) {
        printf("%s\\n", matrix1[i]);
    }
    printf("Maximal Rectangle Area for Matrix 1: %d\\n", maximalRectangle(matrix1, rows1, cols1)); // Expected: 6

    // Example 2
    char* matrix2[] = {
        "0"
    };
    int rows2 = 1;
    int cols2 = 1;
    printf("\\nMatrix 2:\\n");
    for (int i = 0; i < rows2; i++) {
        printf("%s\\n", matrix2[i]);
    }
    printf("Maximal Rectangle Area for Matrix 2: %d\\n", maximalRectangle(matrix2, rows2, cols2)); // Expected: 0

    // Example 3
    char* matrix3[] = {
        "1"
    };
    int rows3 = 1;
    int cols3 = 1;
    printf("\\nMatrix 3:\\n");
    for (int i = 0; i < rows3; i++) {
        printf("%s\\n", matrix3[i]);
    }
    printf("Maximal Rectangle Area for Matrix 3: %d\\n", maximalRectangle(matrix3, rows3, cols3)); // Expected: 1

    // Example 4 (Full of 1s)
    char* matrix4[] = {
        "111",
        "111",
        "111"
    };
    int rows4 = 3;
    int cols4 = 3;
    printf("\\nMatrix 4:\\n");
    for (int i = 0; i < rows4; i++) {
        printf("%s\\n", matrix4[i]);
    }
    printf("Maximal Rectangle Area for Matrix 4: %d\\n", maximalRectangle(matrix4, rows4, cols4)); // Expected: 9
    
    return 0;
}

Run

Sample Output

Matrix 1:
10100
10111
11111
10010
Maximal Rectangle Area for Matrix 1: 6

Matrix 2:
0
Maximal Rectangle Area for Matrix 2: 0

Matrix 3:
1
Maximal Rectangle Area for Matrix 3: 1

Matrix 4:
111
111
111
Maximal Rectangle Area for Matrix 4: 9

Complexity Analysis:

• Time Complexity:
• Iterating through m rows: O(m)
• Updating heights array for each row: O(n)
• Calling largestRectangleArea for each row: O(n) (due to stack-based approach).
• Total: O(m * (n + n)) = O(m*n)
• Space Complexity:
• heights array: O(n)
• Stack for largestRectangleArea: O(n)
• Total: O(n)

Conclusion

The problem of finding the maximal rectangle of '1's in a binary matrix is efficiently solved by reducing it to a series of "Largest Rectangle in Histogram" problems. By iterating through each row, dynamically updating a histogram representing the heights of consecutive '1's above that row, and then applying an O(N) stack-based algorithm for the histogram, we achieve an overall O(m*n) time complexity. This approach is significantly more efficient than brute-force methods and provides a robust solution for a common grid-based challenge.

Summary

• The "Maximal Rectangle" problem seeks the largest area submatrix of '1's.
• A naive brute-force approach has O((m*n)^3) complexity, which is too slow.
• The optimal solution transforms the 2D problem into a sequence of 1D "Largest Rectangle in Histogram" problems.
• For each row, a heights array is constructed, representing the vertical extent of '1's.
• The largestRectangleArea function, using a stack, efficiently finds the maximum rectangle in O(N) time for a given histogram.
• The combined approach has a time complexity of O(m*n) and a space complexity of O(n), where m is the number of rows and n is the number of columns.
• This technique is widely applicable in image processing, game development, and data analysis.