Example: Maximal Rectangle in C

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