Example: Maximal Rectangle Binary Submatrix in C

// 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;
}