Maximum Size Rectangle Binary Sub Matrix With All 1s Practice

In this article, you will learn how to efficiently find the maximum size rectangle containing only 1s within a given binary matrix. This is a classic problem with applications in various fields.

Problem Statement

Consider a binary matrix, which is a grid where each cell contains either a 0 or a 1. The challenge is to identify the largest rectangular submatrix that consists entirely of 1s and report its area. This problem frequently arises in scenarios requiring pattern recognition or optimal resource allocation within grid-based data. For instance, in an image processing context, finding such a rectangle could help detect a contiguous feature.

Example

Consider the following binary matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

The maximum size rectangle of 1s in this matrix has an area of 8. It's formed by the submatrix starting at (row 1, col 2) and ending at (row 2, col 4):

. . 1 1 1
. . 1 1 1

(Visualizing with '.' for 0s and '1' for 1s to highlight the rectangle in the example output)

Background & Knowledge Prerequisites

To understand the most efficient solution for this problem, familiarity with the following concepts is beneficial:

• Arrays and Matrices: Basic operations and traversal.
• Dynamic Programming (DP): Storing results of subproblems to avoid redundant calculations.
• Stack Data Structure: Its use in efficiently tracking elements in an ordered manner.
• Largest Rectangle in Histogram Problem: This is a crucial subproblem where you find the largest rectangle in a bar chart. The maximal rectangle problem reduces to solving this subproblem for each row.

For the C code examples, you'll need standard C library knowledge, specifically for input/output and for dynamic memory allocation if matrices are dynamic. No special external libraries are required.

Use Cases or Case Studies

Finding the maximum size rectangle of 1s has several practical applications:

• Image Processing: Identifying large, contiguous regions of a specific feature (e.g., a defect, a textured area) in a black-and-white image.
• Bioinformatics: Locating conserved regions in DNA sequences, where matching characters can be represented as 1s.
• Data Analysis: Discovering the largest contiguous block of "true" values in a boolean dataset, indicating a consistent pattern or event.
• Game Development: Pathfinding or level design, where identifying the largest walkable or buildable area in a grid.
• Resource Allocation: In manufacturing or logistics, finding the largest empty space in a warehouse or on a production floor.

Solution Approaches

Approach 1: Brute Force (Conceptual Overview)

A straightforward but highly inefficient approach is to check every possible rectangular submatrix. For an M x N matrix, there are approximately (M^2 * N^2) possible rectangles. For each rectangle, we would then iterate through its cells to check if all are 1s, taking O(M*N) time. This leads to a total time complexity of O(M^3 * N^3), which is impractical for larger matrices.

Approach 2: Dynamic Programming with Largest Rectangle in Histogram

This approach leverages dynamic programming to transform the 2D problem into a series of 1D "Largest Rectangle in Histogram" (LRH) problems. It significantly improves efficiency.

One-line summary

Iterate through each row, building a histogram of consecutive 1s above it, and then find the largest rectangle in that histogram using a stack.

Code Example

// Maximal Rectangle Binary Submatrix
#include <stdio.h>
#include <stdlib.h> // For malloc, free
#include <string.h> // For memset, memcpy

// Function to find the largest rectangle in a histogram
// heights: An array representing the heights of bars in the histogram
// n: The number of bars in the histogram
int largestRectangleArea(int* heights, int n) {
    int maxArea = 0;
    int* stack = (int*)malloc(sizeof(int) * n); // Store indices
    int top = -1; // Stack top pointer

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i]; // Current height, 0 for end of array

        while (top != -1 && h < heights[stack[top]]) {
            int currentHeight = heights[stack[top--]];
            int width = (top == -1) ? i : (i - stack[top] - 1);
            if (currentHeight * width > maxArea) {
                maxArea = currentHeight * width;
            }
        }
        stack[++top] = i; // Push current index onto stack
    }

    free(stack);
    return maxArea;
}

// Function to find the maximal rectangle of 1s in a binary matrix
// matrix: The input binary matrix (represented as a 2D array of ints)
// rows: Number of rows in the matrix
// cols: Number of columns in the matrix
int maximalRectangle(int** matrix, int rows, int cols) {
    if (rows == 0 || cols == 0) {
        return 0;
    }

    int maxArea = 0;
    int* heights = (int*)calloc(cols, sizeof(int)); // Initialize with zeros

    // Iterate through each row
    for (int i = 0; i < rows; i++) {
        // Build histogram for the current row
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 1) {
                heights[j]++; // Increment height if current cell is 1
            } else {
                heights[j] = 0; // Reset height to 0 if current cell is 0
            }
        }

        // Find the largest rectangle in the current histogram
        int currentMaxArea = largestRectangleArea(heights, cols);
        if (currentMaxArea > maxArea) {
            maxArea = currentMaxArea;
        }
    }

    free(heights);
    return maxArea;
}

int main() {
    // Example 1
    int matrix1_data[4][5] = {
        {1, 0, 1, 0, 0},
        {1, 0, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0}
    };
    int rows1 = 4;
    int cols1 = 5;

    int** matrix1 = (int**)malloc(rows1 * sizeof(int*));
    for (int i = 0; i < rows1; i++) {
        matrix1[i] = (int*)malloc(cols1 * sizeof(int));
        for (int j = 0; j < cols1; j++) {
            matrix1[i][j] = matrix1_data[i][j];
        }
    }

    printf("Matrix 1:\\n");
    for (int i = 0; i < rows1; i++) {
        for (int j = 0; j < cols1; j++) {
            printf("%d ", matrix1[i][j]);
        }
        printf("\\n");
    }
    printf("Maximal rectangle area for Matrix 1: %d\\n\\n", maximalRectangle(matrix1, rows1, cols1));

    // Free memory for Matrix 1
    for (int i = 0; i < rows1; i++) {
        free(matrix1[i]);
    }
    free(matrix1);

    // Example 2: Simple case
    int matrix2_data[2][2] = {
        {1, 1},
        {1, 1}
    };
    int rows2 = 2;
    int cols2 = 2;

    int** matrix2 = (int**)malloc(rows2 * sizeof(int*));
    for (int i = 0; i < rows2; i++) {
        matrix2[i] = (int*)malloc(cols2 * sizeof(int));
        for (int j = 0; j < cols2; j++) {
            matrix2[i][j] = matrix2_data[i][j];
        }
    }

    printf("Matrix 2:\\n");
    for (int i = 0; i < rows2; i++) {
        for (int j = 0; j < cols2; j++) {
            printf("%d ", matrix2[i][j]);
        }
        printf("\\n");
    }
    printf("Maximal rectangle area for Matrix 2: %d\\n\\n", maximalRectangle(matrix2, rows2, cols2));

    // Free memory for Matrix 2
    for (int i = 0; i < rows2; i++) {
        free(matrix2[i]);
    }
    free(matrix2);

    return 0;
}

Run

Sample Output

Matrix 1:
1 0 1 0 0 
1 0 1 1 1 
1 1 1 1 1 
1 0 0 1 0 
Maximal rectangle area for Matrix 1: 8

Matrix 2:
1 1 
1 1 
Maximal rectangle area for Matrix 2: 4

Stepwise Explanation

1. Initialize heights array: Create an array heights of size cols, initialized to all zeros. This array will store the consecutive count of 1s ending at the current cell and extending upwards.

1. Iterate through rows: Process the input matrix row by row. For each row i:
   • Update heights array: For each column j in the current row:

If matrix[i][j] is '1', increment heights[j]. This means the column of 1s just got one taller.

If matrix[i][j] is '0', reset heights[j] to 0. A zero breaks any continuous column of 1s above it.

Solve Largest Rectangle in Histogram (LRH): After updating the heights array for the current row, treat heights as a histogram. Call a helper function largestRectangleArea to find the largest rectangle that can be formed within this histogram.

Update maxArea: Compare the area returned by largestRectangleArea with the overall maxArea found so far and update maxArea if the current one is larger.

1. largestRectangleArea Function (Monotonic Stack):
   • This function takes an array of heights (the histogram) and its size n.

It uses a monotonic stack to efficiently find the largest rectangle. The stack stores indices of bars in increasing order of their heights.

When a bar h is encountered that is shorter than the bar at the top of the stack, it means the bar at the top of the stack can no longer extend to the right. So, pop elements from the stack until the condition is met.

For each popped bar, calculate its area: currentHeight * width. The width is determined by the difference between the current index i and the index of the bar *before* the one just popped from the stack (or i if the stack becomes empty).

Push the current index i onto the stack.

After iterating through all bars (and an implicit 0-height bar at the end to clear the stack), the maxArea found is returned.

1. Return maxArea: After processing all rows, the maxArea variable will hold the area of the maximal rectangle of 1s in the entire binary matrix.

This approach has a time complexity of O(Rows * Columns) for updating the heights array for each row and O(Columns) for the largestRectangleArea function (as each element is pushed and popped at most once). Thus, the total time complexity is O(Rows * Columns). The space complexity is O(Columns) for the heights array and the stack used in largestRectangleArea.

Conclusion

The problem of finding the maximum size rectangle of 1s in a binary matrix is a classic challenge with wide-ranging applications. While a brute-force approach is conceptually simple, its cubic time complexity makes it impractical for real-world scenarios. The most efficient solution leverages dynamic programming to reduce the 2D matrix problem into a series of 1D Largest Rectangle in Histogram problems. By using a monotonic stack to solve the LRH problem for each row, we achieve an optimal time complexity of O(Rows * Columns), making it suitable for larger datasets.

Summary

• The problem involves finding the largest rectangular submatrix containing only 1s in a binary grid.
• It has applications in image processing, bioinformatics, and data analysis.
• A naive brute-force solution is inefficient, with O(M^3 * N^3) time complexity.
• The optimal approach utilizes dynamic programming.
• This DP approach transforms each row into a histogram, where bar heights represent consecutive 1s extending upwards.
• The "Largest Rectangle in Histogram" problem is solved for each generated histogram using a monotonic stack.
• The overall time complexity is O(Rows * Columns), and space complexity is O(Columns).